# Question
Title: How fast can we compute the size of maximum matching in an unweighted bipartite graph?
> Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching?

It is a long shot but it is often an interesting problem to avoid throwaway computations like these.

---

### Motivation

The problem I am trying to solve is *match-2* where the two sets are of different sizes. I need to determine whether there is a matching that covers all the vertices from the smaller set. Knowing the size of the maximum matching would let me check if it is is equal to or smaller than the size of the smaller set (if such a thing is possible then whenever the result is "yes, there is a matching that covers the small set" you would effectively know what its size is but only in that case), but that is not strictly necessary: if there is a way to compute the answer without computing the size it is good for me.

# Answer
> 3 votes
I believe the best algorithm known is Hopcroft and Karp, "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs", SIAM Journal of Computing 2:4 (1973), pp 225-231.

---
Tags: algorithms, graphs, optimization, matching, bipartite-matching
---


# Question
Title: Variant of TSP: allow each vertex to be visited at most twice
We are given a finite set $V$ and a set of distance $d : V\times V \rightarrow R\ge 0$ and we wish to compute a tour. Suppose we allow each vertex to be visited at most twice in the tour. How can we prove this is NP complete?

# Answer
Let $T = (V,d,k)$ be an instance of Metric-TSP, where $V$ is a vertex set, $d: V\times V \rightarrow \mathbb{R}\_{\geq 0}$ is a distance with triangle inequality, and $k\in \mathbb{R}\_{\geq 0}$.

Suppose that $T$ is a positive instance of Metric-TSP (i.e. there exists a tour with total length $\leq k$. Then $T$ is also a positive instance for your variant (just take the same tour).

Suppose $T$ is a positive instance of your variant, and let $t = (v\_1, v\_2,\ldots,v\_r)$ denote a "tour" with total length $\leq k$. Whenever there is a vertex $v$ which appears twice in $t$ one can safely delete one of the two appearances as every vertex will still be visited and by the triangle inequality the total length of $t$ can only decrease. Once you have deleted all the duplicates, you are thus left with a tour of length $\leq k$, which shows that $T$ is also a positive instance of Metric-TSP.

Thus, there is a trivial reduction (namely the identity) from Metric-TSP to your variant. As Metric-TSP is NP-complete and your variant is in NP, your variant is also NP-Complete.
> 1 votes

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: What is the formal statement of the dining philosopher's problem?
I've read about it in a few places and I'm not sure I get it. Are the philosopher's allowed to act simultaneously? Do they each take 1 action simultaneously, then go on to their next action?

# Answer
> 1 votes
In most models of concurrency, each participant performs one elementary action at a time. This applies both to philosophers and to forks. So if two philosophers try to grab the same fork around the same time, one of them will make the attempt first.

Concurrency models usually do not have a global time, so there is no concept of actions happening “at the same time” if they don't involve the same object. Each participants sees events according to its own notion of time. If an action happens which doesn't involve a particular participant, that participant only learns about it later when it receives some message informing it that the action has taken place.

Think of the participants as nodes in a network (which they often are). If two actions happen on different nodes, it doesn't matter whether they're “exactly” simultaneous. And physically speaking, they wouldn't be exactly simultaneous: without perfectly synchronized clocks, there's always some slight measurement error or reaction delay that means that you can't distinguish perfectly simultaneous actions from actions that happened within an extremely small time frame.

Each philospher decides to pick up and set down forks at their own pace. One philosopher may pick up a fork, eat and set it down before his neighbor has lifted a finger. Or they may race for the same fork, but only one of them will manage to grab it. Meanwhile the other philosophers are doing whatever they please.

Having one timeline per participant, rather than a global timeline, both simplifies the model and makes it closer to the reality of most concurrent systems. The model is simpler because there's never any reason to treat actions as simultaneous, and never any reason to care about the exact order of actions happening in different places. It's closer to the reality of concurrent processes and distributed systems because each thread or each network node *does* have its own perception of when actions take place.

An exception is the modeling of circuits where all actions happen on a clock cycle. This is one of the fundamental ways in which parallelism differs from concurrency. In a circuit, it often does make a difference that two actions happen at different parts of the system on the same clock cycle (e.g. two inputs change simultaneously), rather than on distinct clock cycles.

# Answer
> 0 votes
Having the philosophers act simultaneously (like if two of them try to pick up the same fork at the same time) would potentially make the d.p.p. even worse.

But with the "bad" algorithm presented on Wikipedia, if all philosophers pick up the fork on their left, at times $t\_1,\dots,t\_5$, then we have deadlock no matter what the times $t\_i$ are.

---
Tags: concurrency
---


# Question
Title: Finding square root without division and initial guess
I am trying to look for a division-free algorithms which finds square-root using only addition and multiplication operations, with the initial guess as the number itself. Is there any such algorithms ?

# Answer
OK, let's go with floating point. Any positive floating point number is of the form $m \times 2^e$ where $m$ is in the range $\[1,2)$ and $e$ is an integer.

If $e$ is even, then:

$$\sqrt{m \times 2^{2p}} = \sqrt{m} \times 2^p$$

And if $e$ is odd, then:

$$\sqrt{m \times 2^{2p+1}} = \sqrt{m} \times \sqrt{2} \times 2^p$$

We can precompute $\sqrt{2}$. So we have reduced the problem to finding a square root of a number between 1 and 2. So far, so good.

We could use the Newton-Raphson method for square roots, but you specifically didn't want division, and it's a bad idea anyway; division is more expensive than multiplication on a modern FPU.

But we could use the Newton-Raphson method for *reciprocal* square roots. The iteration looks like this. If $x\_0$ is an initial approximation to $\frac{1}{\sqrt{m}}$, then iterate:

$$x\_{i+1} = \frac{1}{2} x\_i \left( 3 - m x\_i^2 \right)$$

When this has converged, $m x\_k$ is an approximation to $\sqrt{m}$. No divisions here, and the problem is now just to come up with an initial estimate.

But wait, we can do better.

Given $b\_0 = m$, let's suppose we could come up with a sequence of numbers $Y\_i$ such that $b\_i = b\_0 Y\_0^2 Y\_1^2 \cdots Y\_n^2$ approaches $1$. Then $x\_i = b\_0 Y\_0 \cdots Y\_{i-1}$ approaches $\sqrt{m}$ and $y\_i = Y\_0 \cdots Y\_{i-1}$ approaches $\frac{1}{\sqrt{m}}$. Please pause for a moment and convince yourself that this is the case.

We already know such a sequence, because we can use the Newton-Raphson iteration for reciprocal square roots:

$$b\_i = b\_{i-1} Y\_{i-1}^2$$ $$Y\_i = \frac{1}{2}(3 - b\_i)$$

And so:

$$x\_0 = m Y\_0$$ $$x\_{i} = x\_{i-1} Y\_i$$

and:

$$y\_0 = Y\_0$$ $$y\_{i} = y\_{i-1} Y\_i$$

But observe that $b\_i = x\_{i-1} y\_{i-1}$. So we don't actually have to retain $b\_i$:

$$Y\_i = \frac{1}{2}(3 - x\_{i-1} y\_{i-1}) = 1 + \frac{1}{2}(1 - x\_{i-1} y\_{i-1})$$

Substituting this into the equations for $x\_i$ and $y\_i$ gives:

$$x\_{i} = x\_{i-1} \left( 1 + \frac{1}{2}(1 - x\_{i-1} y\_{i-1}) \right) = x\_{i-1} + \frac{1}{2}(1 - x\_{i-1} y\_{i-1}) x\_{i-1}$$ $$y\_{i} = y\_{i-1} \left( 1 + \frac{1}{2}(1 - x\_{i-1} y\_{i-1}) \right) = y\_{i-1} + \frac{1}{2}(1 - x\_{i-1} y\_{i-1})y\_{i-1}$$

Removing the redundant computation gives:

$$r\_i = \frac{1}{2}(1 - x\_{i-1} y\_{i-1})$$ $$x\_{i} = x\_{i-1} + r\_i x\_{i-1}$$ $$y\_{i} = y\_{i-1} + r\_i y\_{i-1}$$

But we're not done! We can save the multiplication by a half by substituting $h\_i = \frac{1}{2} y\_i$.

Given $Y$ as an approxmiation to $\frac{1}{\sqrt{m}}$, set:

$$x\_0 = m Y$$ $$h\_0 = \frac{1}{2} Y$$

Iterate:

$$r\_i = \frac{1}{2} - x\_{i-1} h\_{i-1}$$ $$x\_{i} = x\_{i-1} + r\_i x\_{i-1}$$ $$h\_{i} = h\_{i-1} + r\_i h\_{i-1}$$

Then $x\_i$ converges to $\sqrt{m}$ and $h\_i$ converges to $\frac{1}{2\sqrt{m}}$. Not only does the inner loop have no divisions, it can be implemented on modern FPUs using three fused multiply-adds and nothing else. Perhaps it's unsurprising that this algorithm, known as Goldschmidt's algorithm, is the one used in your FPU.

The final question: How do we come up with $Y$? Well, you could use $\frac{1}{m}$ or something if you want to allow one division. But you said no divisions. So since $m$ is known to be between 1 and 2, you could use its high-order bits to consult a lookup table, or use an interpolating polynomial approximation, such as a Chebyshev polynomial. I'll leave the details of that to you.
> 10 votes

# Answer
Instead of finding the square root of x, find the square root of 1/x, then multiply by x. Newton iteration for this function gives a formula without divisions.

For an initial value of the iteration, look how floating point numbers are represented as bits, and find a bit pattern that represents a number close to the square root of 1/x.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Searching a hierarchy for progressive node criteria
In our organization we have various business units that organize their data in different ways. The folder structure can vary, but they abide by business unit practices when making backups etc.

I am to make a scraper that locates backups and copies them. I have found a general way to describe the business unit specific way of making backups. I do not wish to search the whole directory structure because it may be massive.

```
/X
  A
   a
  B
   a
  C
   a

```

Here for instance, in order to locate all the lower case "a", I can say that the criteria is a list of strings

```
"*","*","a"

```

The X will satisfy the first asterisk. The A/B/C subfolders will satisfy the second asterisk and the lower case a's will satisfy the lower case a criteria. Already, we see a potential for the two "*" to be represented as "*" and a multiplier modifier.

All well and good. In C#, this is easy. The DirectoryInfo class has the GetDirectories method which performs a scan with a searchpattern.

However, what if the structure is *staggered*? What if I would like to list the criteria as follows?

```
Pattern="*" MaxRepetitions=3 MinRepetitions=1
Pattern="a" MaxRepetitions=1 MinRepetitions=1

```

The code becomes messy quick. For instance "a" will also be satisfied by "\*" criteria, so the engine may not be "sure" which criteria is being exhausted and therefore must test multiple criteria on next pass. I assume regex has solved this problem because it runs so fast on large strings and still manages to return without duplicates.

Are there any pointers? Is there any theory behind how to preserve a context (visitor state), assuming this is the visitor pattern.

# Answer
These things are generally done through backtracking. Which in your case would look somewhat like this:

1. Go down 3 levels and look for 'a'
2. If you find some -\> perform your magic
3. If you find none (or if you do, depending on the implementation) -\> go up 1 level repeat steps 1-3

Really this is no better than simply searching all directories in the worst case, but there is no way you can guarantee having found all a's without searching every directory anyway (assuming no prior knowledge). However this solution will have a much better average case performance if the a's are always at the maximum level than simply starting to search at level 1, then level 2 etc.

edit: also, regexes are fast because the average CPU performs billions of operations per second. If you're copying files then the copying will be the part slowing it own drastically anyway so you probably should not be too concerned with the performance of your searching algorithm
> 0 votes

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


# Question
Title: Upper bounds for $NP$ based on $NEXP = EXP$
It's open whether $EXP = NEXP \to P = NP$ (the other direction can be shown by padding). My question: has there been any progress along these lines at all? For example, can we show that $EXP = NEXP \to NP \subset SUBEXP$ (where $SUBEXP = \cap\_{\epsilon \> 0} 2^{n^\epsilon}$)?

# Answer
> 1 votes
If someone has demonstrated that $EXP=NEXP\implies NP\subseteq SUBEXP$, then that guy has *unconditionally* proved a long-sought separation $P^{NP}\subsetneq NEXP$.

*Proof*: If $EXP\neq NEXP$, then obviously, $P^{NP}\neq NEXP$.

So assuming $EXP=NEXP$, the above statement gives us $NP\subseteq SUBEXP$. We have:

$$P^{SUBEXP}=SUBEXP$$

So, $P^{NP}\subseteq SUBEXP\subsetneq EXP$.$\blacksquare$

---
Tags: complexity-theory, nondeterminism
---


# Question
Title: What algorithm can solve the conversion engine problem?
I was once asked a question, given a series of units and their ratios, such as inch, cm, gram vs pound, and a lot of potentially cryptic units and ratios, such as A, B, C, D, ... if I am given `n` times to do the `add()` to the table, and `m` time to do `lookup()` to get the conversion, such as from "mile" to "inch" and to "cm" and to "meter" if that was the originally given ratio pairs, then what is the time complexity? (Big O). (I think this is the question -- can't remember every single detail. Probably not temperature F conversion to C, because 0°F is not 0°C, while all other conversions are like 0 inch = 0 cm, meaning they can be converted by multiplying by a `k` factor).

Does this problem actually belong to Union-Find, and therefore can be solved by Weighted Quick Union as described by Sedgewick? Or does it belong to any other areas in CS?

# Answer
In a union-find data structure, each item is either a root or points at a parent. For us, units will be items, and each pointer to a parent will be annotated with the appropriate conversion. You can maintain this annotation while running the usual operations on the union-find data structure.

Using this annotation union-find data structure, you can implement each add() using union and each lookup() using find, with only a constant factor overhead.
> 2 votes

---
Tags: algorithms, union-find
---


# Question
Title: Conceptual explanation of negative weights?
What conceptually are negative weights on graphs? Why might they have them?

# Answer
What is the significance of negative weight edges in a graph?

Above link answers your query.

One more example:- If we want to design some architecture then in the whole circuitry there is flow of current. The whole circuitry can be modeled as graph with device components as vertices and the path between them as edges. In these paths the resistance can be taken as negative weights.
> 0 votes

---
Tags: weighted-graphs
---


# Question
Title: When the data size and processor speed are both multiplied by 10, then a linearithmic algorithm takes double the time to finish?
Robert Sedgewick mentioned, if a computer can handle 10x data and the processor is also 10x as fast, then a $ O(n^2) $ algorithm actually runs slower than before.

Is this the correct idea when a computer has 10x RAM and can handle 10x data all at once, and also have a processor that is 10x faster, then:

1. A $ O(n^2) $ solution is slower, because now $ n^2 $ is 100 times, but processor is only faster by 10 times. So the time it takes to solve the problem is 10 times more. So if it took 1 hour to solve the problem before, now it would take 10 hours.
2. If it is a $ O(n \log n) $ solution, then roughly speaking, for $ n \log n $, it is

$ (100 \log 100) / (10 \log 10) = (100 / 10) \times (\log 100 / \log 10) = 10 \times log\_{10} 100 = 20 $

and since the processor is 10 times as fast, that means now the algorithm is "half as fast"? (meaning if it took 1 hour to solve the whole problem before, now it would take 2 hours)

# Answer
I don't like how you expressed this - the ten times faster computer is ten times faster. It will solve the same problem and answer the same question ten times faster. Of course if you give it a question that would take 100 times longer on the old computer, then it will take only 10 times longer on the new computer.

If you had an algorithm that took n log n microseconds (and in CS "log" usually means log base 2) to solve a problem of size n, a problem of size 10 n would take 10n log (10n) microseconds on the old computer, and n log(10n) microseconds on the new computer.

log (10n) isn't ten times or twice as much as log n - the factor 10 turns into a constant. log (10n) = log n + log 10 ≈ log n + 3.3. If n = 10 it's twice as much. If n = 10 billion it's only ten percent more.

Two things to consider: No computer is just "ten times faster". A computer does many different kinds of operations. Some may be ten times faster, some even more, some less. And Big-O is concerned about asymptotic values: I could have an algorithm that takes on my computer n^2 microseconds if n ≤ 1,000,000 and 10n^2 microseconds if n \> 1,000,000. So if you want to find actual execution times, you need more than Big-O.

And it is *very* common that actual execution times are quite different from what Big-O makes you belief when n is small. For example, let f(n) = n + 1000 log n. f(n) = O(n). But for n ≤ 10,000 f doesn't behave very linear at all.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Largest subset such that for every two elements one of them divides the other
So the problem states:

> An array of $N (1 \leq N \leq 2000)$ natural numbers is given. Find the cardinality of the largest subset of that array such that for every two numbers $A$ and $B$ either $A|B$ or $B|A$ (or both).

I know you don't like it when people post questions without trying anything, but the only thing I can possibly think of (that would work) is brute force, which would mean exploring every possible subset and then checking the given condition, again, by brute force.

But since the time complexity of subset exploration is $O(2^N)$, and $N = 2000$ in the worst case, this solution becomes pretty useless.

Other thing I had in mind was some kind of divide and conquer algorithm, similar to merge-sort. But I can't think of a way I'd use the results of two (left and right) subarrays to compute the result for their union.

So, any ideas?

Thanks.

EDIT: The brute force solution I've made that seems to be working (C++):

```
int largestSubset(const vector<int>&arr, int i, vector<int>&subset, int j){
    if(i == arr.size()){
        //brute force check
        for(int k = 0; k < j; k++){
            for(int s = k + 1; s < j; s++){
                if ((subset[k] % subset[s] != 0) && (subset[s] % subset[k] != 0)){
                    return 0;
                }
            }
        }
        return j;
    }

    //skip the i-th element
    int count1 = largestSubset(arr, i+1, subset, j);
    //include the i-th element
    subset[j] = arr[i];
    int count2 = largestSubset(arr, i+1, subset, j+1);

    return  max(count1, count2);

}

```

# Answer
You can do it in $O(N^2)$ like that:

First, sort your array $L$ in increasing order.

Then, for $i \in \\{0,\ldots,N-1\\}$, let $M\[i\]$ denote the cardinality of the largest valid subset $S$ such that $L\[i\]$ is the largest element of $S$.

We can compute $M\[i\]$ in a dynamic programming fashion: $$ M\[0\] = 1$$ $$\forall i \\;\\; s.t.\\;\\; 0\<i\<N-1: M\[i\] = 1 + \max\_{0\leq j \< i\\L\[j\]\ |\ L\[i\]}\\{M\[j\]\\}$$ (where the max is taken to be equal to $0$ if no $L\[j\]$ divides $L\[i\]$)

To see that, notice that it is clear that $M\[i\] \leq 1 + \max\_{0\leq j \< i\\L\[j\]\ |\ L\[i\]}\\{M\[j\]\\}$ as the second largest element in the corresponding subset must divide $L\[i\]$. Moreover, the fact that the second largest element $L\[j\]$ divides $L\[i\]$ and that the subset without $L\[i\]$ is valid is enough to guarantee that the subset with $L\[i\]$ is valid, as all elements in the subset are compatible between them and all divide $L\[j\]$ and thus divide $L\[i\]$. Thus the dynamic programming formulation is correct.

Then, the value you are looking for is simply the maximum over all $M\[i\]$'s.

This leads directly to a $O(N^2)$ algorithm as the sorting can be done in $O(N\log(N))$, and finding the maximum in $M$ is done in $O(N)$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: How can I download a streaming file without the file's specific address?
I want to download a streaming file, but I don't know the real address of that file, only the address where the stream is. How can I download that file? Is it possible to know the address of the file by sniffing the connection?

# Answer
What do you suppose happens in the back-end when you request a download of a file from a given location? The file gets converted to some encoding (in the most basic/general case: binary) and streamed over a network connection to you as a receiver.

Really for all practical purposes you wouldn't be able to distinguish downloading a 'real' file from download/receiving an active (bit)stream of that file as they're generally the same thing: bits being pushed across a connection.
> 2 votes

---
Tags: computer-networks
---


# Question
Title: Why does Union-Find have time complexity O(N + M lg* N) with the "log star N"?
The time complexity of Weighted Union-Find with Path Compression, for M union-find ops and N objects is said to be

$$ O(N + M \lg^\*N) $$

and the $ lg^\*N $ is "log star N" and is iterated logarithm. It can be almost taken to be a constant, as $ lg^\*2^{65536} $ is only equal to 5. Why is it $ lg^\*N $ and what kind of operations / algorithm typical can produce $ lg^\*N $?

# Answer
Check out the analysis of path compression in Union-Find by Seidel and Sharir "Top-Down Analysis of Path Compression", SIAM Journal of Computing 34:3 (2005), pp 515-525. Somewhat heavy going, the result you cite is a step on the way to the best-possible bound by their method.
> 1 votes

---
Tags: asymptotics, union-find
---


# Question
Title: Recognizing strongly connected digraphs in NL
This homework solution gives a proof that $L = \\{G \mid \text{G is strongly connected directed graph}\\} \in N\mathcal{L}$. One suggested way to proof that $L \in N\mathcal{L}$ by proving that $\bar{L} = \\{G \mid \text{G is not strongly connected} \\} \in NL$ and then using the fact $NL = coNL$.

The tutorial uses the following algorithm for $\bar{L}$:

> 1. Nondeterministically select two nodes $(a,b)$
> 2. Run $PATH(a,b)$. If it rejects, then the graph is not strongly connected, so accept. Otherwise reject.

Since $PATH$ itself is a nondeterministic algorithm (or rather, we have to use a nondeterministic algorithm to still be $N\mathcal{L}$, it is not clear to me why this is correct. Why is it okay to invert the answer of $PATH$ in this case?

For example, assume our nondeterministic choices wrongly lead us to believe there is no path between $a$ and $b$, then this nondeterministic branch would accept (which means our whole TM $M$ would accept, because there is one accepting branch). But if there is also a branch of $PATH$, then our graph $G$ might actually be strongly connected and $M$ will return a wrong answer by accepting.

# Answer
> 2 votes
Because nondeterministic space classes are closed under complementation by the Immerman–Szelepcsényi theorem. So, you can't literally just invert the answer from $\text{PATH}(a,b)$ but the fact that there is an $\mathrm{NL}$ algorithm for $\text{PATH}(a,b)$ implies that there is also an $\mathrm{NL}$ algorithm for $\text{NOT-PATH}(a,b)$, and you use that.

---
Tags: complexity-theory
---


# Question
Title: How many basic operations are there in an algorithm for the simple multiplication of two numbers of equal length?
***BACKGROUND:***

**Note:** The following question arose in my mind when watching this lecture (watch at 5:30 minutes if you will).

**Assumption:** Just for the sake of this question, let's assume that the term "basic operation" means an addition or a multiplication operation between two single-digit numbers.

**Now we have to calculate the number of basic operations involved in the simple multiplication (*the one we learnt in 3rd grade*) of any two numbers, provided that both the numbers have the same length (i.e. the number of digits).**

Let's say `n` represents the length of the numbers.

Let the numbers be `1234` and `5678`. The following image shows the multiplication:

As you can see, each row (i.e. each partial product of the first number with a digit of the second number) involves `4` multiplication operations, and `4` addition operations (think of the carries). *Depending on the number of carries (and thus depending on the original numbers), in the case of any two numbers, in each row, it could be at least `0` additions (no carry) and at most `4` additions (a carry from each digit-to-digit multiplication).*

**In other words, each row involves `≤ 2n` operations. As there are `n` rows, so the basic operations in all the rows are `n(2n)`, or 2n2.**

---

***QUESTION:***

Now comes that one final addition (shown in black pen in the image). From the video lecture

> The final addition requires a comparable number of operations. Roughly, say, another at-most 2n2 operations.

**The question is**

1. **What is meant by "comparable" number of operations?**
2. **Now, there will be at-most `n-1` `_`'s in the partial products, which means `n-1` addition operations. Apart from those, there will be *at-least* `n` additions (if there isn't a carry from the addition of the left-most digits in the partial products), and *at-most* `n+1` additions (if there IS a carry from the addition of the left-most digits in the partial products). This makes a total of, at-most, `n-1+n+1` or `2n` addition operations in this step. So why are they saying 2n2?**

# Answer
> 4 votes
It's hard to tell what anyone means by "comparable" in a specific context. I would take it to mean "of the same order", so something like $n^2$, maybe $100\cdot n^2$ or $0.0001\cdot n^2$, but not $n$ or $n^3$.

The final addition is doing (roughly) $n$ additions of numbers of (roughly) non-$\\\_$ $n$ digits, and each of those additions takes (roughly) $n$ additions of single digit numbers. So that's why you end up with (roughly) $n^2$ additions.

# Answer
> 0 votes
Instead of collecting each partial product then adding all of them at the end, let's keep a register that is `2n` digits long, initially full of zeros, and we will update it as we go.

After each `n + 1` digit-long partial product, we add it into the sum register. We need to shift it one digit higher each round. We need to do `n + 1` additions, then need to do more additions to cascade any carries. So there will be upper limit of `2n` additions into the sum register each round. Since there are `n` rounds, we get a total of `2n²` operations for the sum register round.

This is why it's comparable to the multiplication round, although the multiplication round is a mix of multiplication and addition while the sum register round is just additions.

---
Tags: algorithms, algorithm-analysis, arithmetic, multiplication
---


# Question
Title: Least Significant Bit (LSB) vs Little Endian - Are they equivalent in anyway!
For a multiple choice question: What do we call the LSB? (i)Little Endian (ii)Upper bit (iii)Big Endian (iv)Lower Bit

I feel ideally none of them is a true correct choice, but my best bet was (iv) Lower Bit.

However, our professor claims that the correct choice should be (i)Little Endian. He even said "*LSB stands for Least Significant Bit which is right most bit of a binary equivalent and it is Little endian format.*"

I don't agree with the last part i.e. "..it is Little endian format."

My understanding (primarily from the book “Computer Organization and Design” by Patterson and Hennessy,) is that LSB (and MSB) concepts were introduced to clearly identify bits at both extremes while avoiding any confusion arising due to writing styles like vertically or horizontally which can be confusing when read/written from different directions. Further it (LSB) has nothing to do with byte ordering such as Little endianness. For example any number will have both LSB and MSB, and can be stored in a little endian hardware as much as it can be stored in a big-endian hardware.

Pls let me know if I'm misunderstanding the professor's statement in any way.

# Answer
LSB (least significant bit) and MSB (most significant bit) apply purely to the values of an integer. The least significant bit is the bit with value 1, the second least significant bit is the bit with value 2, and so on.

"Little endian" and "Big endian" are just artefacts from the fact that the bytes of a number can be accessed individually as they are stored in memory. But if an integer is stored in 4 bytes, there are actually 24 different ways in which order these bytes could be stored in memory; big endian and little endian are just two of those 24.

With all this said, if you have been understanding your professor correctly, and reported accurately what he said, then he is absolutely wrong. Actually the multiple choice answer "lower bit" is already nonsense (maybe not nonsense, but we really like precision in CS). If you have 32 bits, 31 of them are "lower" than some other bit, but ONE of them is the lowest bit. The Least Signficant Bit.

When "Little Endian" and "Big Endian" are abbreviated, they are abbreviated as LE and BE (for example UTF-16 LE and UTF-16 BE).
> 5 votes

---
Tags: terminology, computer-architecture
---


title: PCAs and Kleene's Recursion Theorem

text:
# Question
Title: PCAs and Kleene's Recursion Theorem
I might need some help with the following question.

Given a Partial Combinatory Algebra, we can define the fixed point combinator $Y := \[\lambda^{\*}xy.y(xxy)\]\[\lambda^{\*}xy.y(xxy)\]$. How does this relate to Kleenes recursion theorem, aka. fixed point theorem?

In the setting of Kleenes first PCA, ie. the PCA of computable functions on $\mathbb{N}$, given a (partial) computable function $f = \varphi\_c$ the fixed point combinator satisfies $Yc = c(Yc)$. As I understand it this means that taking d := Yc it translates to $f(d) = \varphi\_c(d) = cd = d$, ie. $f$ having a fixed point.

However Kleene's recursion theorem originally gives a weaker assertion, namely that for every total computable function $g$ there is some $n$ such that $\varphi\_{g(n)} \simeq \varphi\_n$ (cf. Odifreddi - Classical Recursion Theory, Theorem II.2.10).

This really confuses me and I couldn't make up my mind what to do about it. I hope someone can help me out. Anyway, thank you for your time.

# Answer
> As I understand it this means that taking $d := Yc$ it translates to $f(d)=φ\_{c}(d)=cd=d$, ie. $f$ having a fixed point.

Not every recursive function has a fixed point in the sense of $f(n)=n$ \- for example, $f(n)=n+1$. Therefore, there must be something wrong with this proof. As noted in comments, this proof works only if $d=Y c$ is defined.

As you've noticed, you can work around this issue by using a variant of the Y combinator:

> Just taking Ycc′=c(Yc)c′ doesn't seem to make your problem any better

But it does! To avoid confusion, I'll call this combinator . We have

$Zcc′=c(Zc)c′$.

Let's take a function $f=\varphi\_c$ and let $d = Z c$, just like in the previous proof. Now, $d$ is guaranteed to be defined. We have

$d c' \equiv c d c'$

By the definition of application in the Kleene's first algebra this means:

$\varphi\_{d}(c')$ $ \simeq \varphi\_{\varphi\_{c}(d)}(c')$

$\varphi\_{d}(c')$ $ \simeq \varphi\_{f(d)}(c')$

$\varphi\_{d}$ $ \simeq \varphi\_{f(d)}$

which is the Kleene's recursion theorem.

> Well, literally the same problem arises in the proof of the Recursion theorem in Odifreddi's Classical Recursion Theory, Theorem II.2.10. There he takes $b$ to be a code satisfying $\varphi\_{b}(e) \simeq f(\varphi\_e(e))$.

No, $b$ is defined in Theorem II.2.10 using the equation:

$\varphi\_{\varphi\_{b}(e)} \simeq \varphi\_{f(\varphi\_e(e))}$

Importantly, $b$ is a *code* \- it is a well-defined natural number that encodes a specific program. Furthermore, for every $e$, $\varphi\_b(e)$ is also a code - it is *not* the result of running $f(\varphi\_e(e))$, it is merely a code of a function which given $n$, runs the function $\varphi\_{f(\varphi\_e(e))}$ on $n$. (This difference mirrors the difference between Y and Z combinators.)
> 1 votes

---
Tags: computability
---


# Question
Title: Why does a RNN network output different based on the training sequence
I've set up an RNN LSTM network in Java using DL4J as the library.

I currently have 500 examples of positive text, and 500 examples of negative text.

When I fitness the training data by first training all the negatives and then all the positives, my predictions only favor high positive responses even for things that would be considered negative in my training examples.

And if I reverse it and train positive first and then train negative last everything is favored as a negative in high 80 - 90%.

However, when I train in an oscillating pattern such as: Positive, Negative, Positive, Negative and so on, the predictions become accurate again and similar examples of negative text are picked up relatively accurately and vice versa for positive text.

I've only just started studying machine learning in general but I can't quite find any resources explaining why the sequence of training impacted my model so hugely. Is this normally how an LSTM network should behave or is oscillating the training data the correct approach?

Would the classification of a messages negative intent be something an LSTM RNN network should be used for or should I consider another network?

# Answer
> -1 votes
RNNs are pattern recognition tools. It is't entirely clear to me what it is exactly that you are trying to do, but if you simply intend for it to classify positive and negative messages a regular Neural Network might be better suited.

What your RNN does (if implemented correctly) is learn classifications in the context of the sequence. i. e. It is learning: what are the odds of a given input X being positive/negative knowing the preceding N outcomes.

This should already be giving you some insight on why different orderings of the training data skew the results. If your training set is all positives followed by all negatives then the vast majority of your training set will be teaching the network that a sequence of positives almost certainly indicate a positive message and vice versa.

Building a good dataset is by far the most important part of applying machine learning and I suggest you look for some high level explanations of the different types of ML and some general information on bias in data.

# Answer
> -1 votes
Don't train by first training all the negatives or first training all the positives. Instead, randomize the order in which examples are used during training. Moreover, you should use a different random order in each epoch.

When you use a non-random order, catastrophic forgetting can cause performance to suffer, as you have observed.

This is not specific to RNNs; the same observations apply to neural networks for classification as well.

---
Tags: machine-learning, artificial-intelligence, java
---


# Question
Title: Does basic 2 PL always ensure conflict serializability?
While going through the DBMS book by Korth, it was mentioned :

" For a set of transactions, there may be conflict-serializable schedules that cannot be obtained through the two-phase locking protocol.

Does this imply that basic 2 PL ensures serializability but does not always ensure conflict serializability ?

# Answer
No,

If you use 2PL protocol you are guaranteed to have a conflict-serializable schedule but there are conflict serializable schedules which may not honour 2 PL protocol i.e. locking data items in the growing phase and releasing them in the shrinking phase.
> 2 votes

---
Tags: databases, database-concurrency
---


# Question
Title: Complexity Class of an Algorithm with two Inputs
Consider a problem with two inputs like (P,L) and |P|=n and L is some positive integer. If my algorithm had a complexity of O(n^L), would that still be polynomial? Or is it exponential? I'm not sure if I should view L as a constant or as 'size of input', since it's not a size but just some number (as in, Knapsack for example, select items of weight \<= L). At the same time, L is part of the input and not fixed.

# Answer
> 1 votes
You're confused because you've called part of your input $n$. When we say that the running time is some function of $n$, we almost always mean that $n$ is the length of the input string.

Your algorithm runs in time $|P|^L$, where $P$ is a string contained in the input and $L$ is a number represented in the input, presumably in binary. If $L$ is a $b$-bit number, it could be as big as $2^b$. Writing $n$ for the length of the input, we could, for example, have $|P|=n/2$ with $L$ being an $(n/2)$-bit number. That case gives running time $(n/2)^{2^{n/2}}$, which is a long, long way from being polynomial.

---
Tags: complexity-theory, runtime-analysis
---


# Question
Title: When are invariants true inside of a loop?
I am new to the idea of invariants and hope to find more information about it.

It can make an algorithm or loop show a high level of certainty / confidence that the code is correct, such as in the case of a binary search, as described in the book Programming Pearls, 2nd Ed.

Are invariants true at most part of the loop and can be untrue at some part? That is, in the middle of the loop:

```
while a <= b
    if (...)
        // Point A
    else
        // Point B
    end
    // Point C
end

```

is it true that at Point A or Point B, something can change that cause the invariants to break, and it depends on the next iteration to "correct the invariants"? The same with Point C, something can change that can cause the invariants to break?

Maybe Point C is more likely the place where the invariants may break, as it is getting ready for the next iteration? So if it is a for-loop:

```
for(i = 0; i < n; i++) {
    // ...
}

```

then the `i++` is a place where the invariant may break? I am looking if there is any rule that says what time may invariants not hold true, or should they always hold true?

It seems for binary search, the invariants are always true, while for mergesort or quicksort, the invariants are only true at a certain point, such as for mergesort, the array is divided into 2, and it is in sorted order, but this invariant is only true only after the code recursively calls itself to sort both the left and right subarrays. But this is recursion, so I don't know if there is any difference between that or just a loop.

# Answer
> Are invariants true at most part of the loop and can be untrue at some part?

Invariants hold prior and after each execution of the loop body; there are no requirements for what happens in between its statements. Not only that, I would even say *it is quite the norm* that invariants are broken during the loop. Fixing them is actually a sort of programming paradigm; it gives you a way of determining what the values for variable assignments in a loop should be. In fact, this is a quite natural concept if your design approach is based on invariants (e.g., if you are writing programs which are annotated with JML as in design by contract and similar ideas based on formal proof systems).

For instance, consider the following toy example in which we want to sum over the elements in an array $A$ and save the result in the variable $s$:

$$\begin{align\*} &s \gets 0 \\ &i \gets |A| \\ &\textbf{while } i \> 0 \textbf{ do} \\ &\quad i \gets i - 1 \\ &\quad s \gets s + A\[i\] \\ &\textbf{done} \end{align\*}$$

The invariant is $s = \sum\_{j=i}^{|A|-1} A\[j\]$, and it holds prior and after each execution of the loop body. However, after $i \gets i - 1$ is executed, the invariant no longer holds, that is, we then have $s = \sum\_{j=i+1}^{|A| -1} A\[j\]$. Hence, the next instruction *updates $s$ so that the invariant holds again*.
> 4 votes

---
Tags: loop-invariants
---


# Question
Title: Is "ternary search" an appropriate term for the algorithm that optimizes a unimodal function on a real interval?
Suppose that I want to optimize a unimodal function defined on some real interval. I can use the well-known algorithm as described in Wikipedia under the name of ternary search.

In case of the algorithm that repeatedly halving intervals, it is common to reserve the term *binary search* for discrete problems and to use the term *bisection method* otherwise. Extrapolating this convention, I suspect that the term *trisection method* might apply to the algorithm that solves my problem.

My question is whether it is common among academics, and is safe to use in, e.g., senior theses, to apply the term *ternary search* even if the algorithm is applied to a continuous problem. I need a reputable source for this. I'm also interested whether the term *trisection method* actually exists.

# Answer
Check out Fibonacci search and golden section search (the article about Fibonacci search talks about an array, but the technique is really applicable just like golden section search to continuous functions). Fibonacci search is a tiny bit faster. The trick is that you can reuse the points from one iteration to the next. For Fibonacci, you'll have to determine the number of iterations beforehand. No big deal, you know the precision sought anyway.

It can be shown that if you just compare the function values for relative order, Fibonacci search is fastest possible. If you consider the actual values, some form of quasi-Newton is faster.
> 1 votes

# Answer
The word "bitonic search" can probably refer to this concept. See this book and these lecture notes for instance.
> 0 votes

---
Tags: algorithms, terminology, numerical-analysis, numerical-algorithms
---


# Question
Title: Is this lambda abstraction created as a generator of a recursive function?
In lambda calculus, a recursive function $f$ is obtained by

$$ f = Y g $$

where $Y$ is the Y combinator and $g$ is the generator of $f$ i.e. $f$ is a fixed point of $g$ i.e. $f == g f$.

In *The Scheme Programming Language*, I saw an example implementing a recursive function $f$ that sums the integers in a list:

```
(let ([sum (lambda (f ls)
                  (if (null? ls)
                     0
                     (+ (car ls) (f f (cdr ls)))))])
(sum sum '(1 2 3 4 5)))  => 15

```

What is the mathematical derivation that drives to create the lambda abstraction

```
 lambda (f ls)
     (if (null? ls)
         0
        (+ (car ls) (f f (cdr ls))))

```

? It looks like a generator of $f$, but not entirely.

Thanks.

# Answer
> 4 votes
If you look at the $Z$ combinator (because we're in an eager context), you have $$Z=\lambda g.(\lambda f.g(\lambda v.ffv))(\lambda f.g(\lambda v.ffv))$$

If you look at the code, we don't apply a fixed point combinator to `sum`, we simply apply `sum` to itself, so there's no reason for `sum` to be "generator".

You can also readily show that `sum` is (modulo currying) equal to $\lambda f.g(\lambda v.ffv)$ for some $g$, basically by replacing `(f f ...)` with `(h ...)` where `h` is the argument to $g$ in the definition for `sum` (minus the outermost `lambda`).

---
Tags: lambda-calculus, recursion
---


# Question
Title: How to make Turing machine deterministic?
My Turing machine starts with an empty tape. It writes a random word of the set $0^n1^n$ to the tape. Hopefully i made no mistakes.

My question is about the productions coming out of state $q\_0$:

$δ(q\_0, blank)=(0,R)$ and $δ(q\_0,blank)=(blank,L)$. (see image below).

Their purpose is to generate a random amount of $0$ before going to state $q\_1$. They are nondeterministic. Is there a workaround to make them deterministic?

I heard that every Turing machine can be made deterministic. But this case is a little bit strange, because instead of testing if a word on the tape is element of a set, it writes a random word of the set to the tape.

# Answer
> 2 votes
If a language is decided by some nondeterministic Turing machine, then it is decided by some deterministic Turing machine. However, not every behavior of a nondeterministic Turing machine can be replicated deterministically, as your example demonstrates.

---
Tags: turing-machines, nondeterminism
---


title: Extend binary search

text:
# Question
Title: Extend binary search
There is a way for finding K entries of N given entries using a binary search?

I mean, I have N entries, indexed from 0 to $N-1$ and I have to find $K$ of them that satisfy some constraint.

The naive way is to iterate one after one and check whether it answers the condition or not. The naive way of Binary Search is using A Binary search until it covers all the tree, this method have a running time $O(K \log n)$. In this way, I will check whether half of the entries answer the condition or not, if they are I will keep investigating the half of the half and so on. It's possible to make it more efficient with saving a dictionary from state to its answer. However, what will be its running time?

Example - Let's say I have a system and I want to check whether deleting some file corrupt it. The naive way is to delete file after file and to check whether the system behaves normally after each deletion. In Binary search, we can index the files from 0 to N-1 and delete each time half of the files. After each deletion, we can check whether the system behaves normally or not. If it behaves normally, the files we deleted in this step do not affect the system. If not, At least one of the files that were deleted affect the system. I asked, how can I find K files that affect the system?

Thanks.

# Answer
Your problem is known as *group testing*. An essentially optimal algorithm for your problem is Generalized binary splitting. There are also pretty good non-adaptive algorithms (such algorithms fix all queries ahead of time).
> 3 votes

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


title: Input distribution in FLP Impossibility

text:
# Question
Title: Input distribution in FLP Impossibility
Lemma 2 in "Impossibility of Distributed Consensus with One Faulty Process" is as follows:

> LEMMA 2. P has a bivalent initial configuration.

They prove this by showing that the opposite assumption creates a contradiction. As part of that proof, they state:

> Let us call two initial configurations adjacent if they differ only in the initial value x, of a single process p. Any two initial configurations are joined by a chain of initial configurations, each adjacent to the next. Hence, there must exist a 0-valent initial configuration C0 adjacent to a 1-valent initial configuration C1.

In other words, there exists two "adjacent" sets of inputs that differ in only in the value of one of the inputs.

But if I use the output of a totally correct consensus protocol to ensure that the inputs are always either all 0 or all 1, the resulting two sets of inputs would not be "adjacent".

So it appears they implicitly assume that every combination of inputs must be possible. Why can they make this assumption?

# Answer
> 3 votes
The authors' goal is to rule out protocols that work for *every* possible input. Hence, in their proof by contradiction, they can assume that the protocol works correctly on every input.

The specification of an algorithm should include all constraints on the possible inputs. For example, binary search assumes that the input array is sorted. The specification of consensus protocols doesn't specify any constraints beyond the processes' inputs being binary.

---
Tags: distributed-systems
---


# Question
Title: Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?
The well-known textbook Introduction to Algorithms ("CLRS", 3rd edition, chapter 3.1) claims the following:

$$ \sum\_{i=1}^n O(i) $$

is not the same as (I'm not using DNE because the book explicitly says "is not the same as")

$$ O(1) + O(2) + \dots + O(n) $$

Why is this? How are we to explicitly represent the first summation if not with the second? As an extension of the previous question, how do we do asymptotic analysis on such a summation?

# Answer
The difference is IMHO well explained in that book, the part you are referring to says

> The number of anonymous functions in an expression is understood to be equal to the number of times the asymptotic notation appears.

So this $$ \sum\_{i=1}^n O(i) $$

means a placeholder for $$ \sum\_{i=1}^n f(i), $$

where $f(i)$ is an anonymous function from the set $O(i)$ — but it is always *the same* function in all terms of the sum. However, in $O(1) + O(2) + \dots + O(n)$, each term represents a placeholder for a (potentially) different anonymous function $f\_i$ from the set $O(i)$. Note the book also says, the latter has "no clear interpretation", so it is quite meaningless.
> 8 votes

# Answer
Doc Brown answered your first question perfectly. Let me answer your second question. The expression $O(i)$ is a placeholder for a function which is bounded by $Ci$ for some $C \> 0$. Therefore $$ \sum\_{i=1}^n O(i) \leq C \sum\_{i=1}^n i = C \frac{n(n+1)}{2} = O(n^2). $$ Furthermore, this bound is tight, in the sense that $n^2$ cannot be replaced with any asymptotically smaller function. This is because $i = O(i)$, and $\sum\_{i=1}^n i = \Theta(n^2)$.
> 8 votes

---
Tags: asymptotics, landau-notation, big-o-notation, summation
---


title: Equivalence of different automata

text:
# Question
Title: Equivalence of different automata
I have a question about the equivalence of different automata. I looked up the similiar questions but sadly none of them are exactly, what I need or am looking for.

I know some of these are equivalent ( or not ) but for which language class pairs does a real inclusion apply?

DFA = NFA ⊋ ? DPDA ≠ PDA ⊋ ? LBA = DTM = NTM

I want to know, if this is correct or not.

Hint:" C is the class of all languages accepted by a C-type machine" - If this is important.

I apologize, if my question isn't in a correct format, therefor forgive me, I am trying to settle in.

# Answer
Linear-bounded automata accept the class of *context-sensitive languages*. In contrast, Turing machine (deterministic as well as nondeterministic) accept the class of *recursive languages*. Every context-sensitive language is recursive, but the converse doesn't hold. For example, the halting problem for nondeterministic Turing machines running in space $n^2$ is not context-sensitive by the nondeterministic space hierarchy theorem.
> 0 votes

---
Tags: formal-languages, automata, equality
---


# Question
Title: Number of induced paths in an interval graph
Let $G$ be an interval graph. For any two vertices $u,v$ in $G$, how many induced paths are between them in $G$? Is it polynomial in terms of the number of vertices in $G$?

# Answer
Consider the following example:

Say the total number of intervals is $n$. To get from one red extremity to the other, you can take a path which alternates between green and blue intervals. Each of those paths is induced, and there are $2^\frac{n-2}{2}$ such paths. Thus, the number of induced paths between two vertices in an interval graph is not necessarily polynomial in the number of vertices.
> 3 votes

---
Tags: algorithms, graphs, discrete-mathematics
---


# Question
Title: DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$
I need some help with the following task:

I have to construct a DPDA for $\\{1^ky \mid \text{$y\in \\{0,1\\}^\*$ with $|y|\_1 \le k$ and $k \in \mathbb N: k\ge1$}\\}$.

How can I recognize that the new substring $y$ begins? For example: $w=zy$, where $z = 1111$ and $y = 1001$.

This is what I have so far:

# Answer
> 2 votes
In order to verify whether the string is of the form $1^ky$ with $y\in \\{0,1\\}^\*$ and $|y|\_1\le k$ you want to determine whether a symbol $1$ in the prefix belongs to the $1^k$ part, or starts $y$.

Now imagine $1^k \cdot 1y$ is of the correct form, i.e., $|1y|\_1 \le k$, then certainly $1^{k+1}\cdot y$ is also correct, as $|y|\_1\< |1y|\_1 \le k \< (k+1)$.

So, keep reading $1$'s while possible.

# Answer
> 2 votes
It is clear $y$ starts with $0$; so all you have to do is to push $1$ on the stack as long as there is no $0$, afterwards delete a $1$ from the stack for each $1$ in the input. This will jam if there are too many $1$s in $y$, you can accept by final state if you reach the end of the input.

---
Tags: context-free, pushdown-automata
---


# Question
Title: Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy?
When defining $\Sigma\_i^P$ or $\Pi\_i^P$ completeness, we want to use a reduction that fulfills the following property: If $L' \leq\_p L$ and $L \in \Sigma\_i^P$ or $\Pi\_i^P$ respectively, then $L'$ is also $\Sigma\_i^P$ or $\Pi\_i^P$.

I can see how Karp-reductions fulfill this requirement for the complexity class $P$. How could one proof that Karp-reduction fulfill this requirement for all other complexity classes in the polynomial hierachy?

# Answer
Suppose that $f$ is the polynomial reduction between $L'$ and $L$, i.e. $x \in L' \Leftrightarrow f(x) \in L$. If $L \in \Sigma\_k^p$ then $y\in L \Leftrightarrow \exists z\_1 \forall z\_2 \ldots M(y, z\_1, \ldots z\_k) = 1$. Then $$x\in L \Leftrightarrow f(x) \in L \Leftrightarrow \exists z\_1 \forall z\_2 \ldots M(f(x), z\_1, \ldots z\_k) = 1 \Leftrightarrow \exists z\_1 \forall z\_2 \ldots P(x, z\_1, \ldots z\_k) = 1$$ $P$ first computes $f$, then applies $M$, so it's polynomial.
> 3 votes

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


title: What is a batch based interface?

text:
# Question
Title: What is a batch based interface?
I came across this description of Batch Interface: "commands and directives are used to manage those commands that are entered into files and those files get executed. "

I would really appreciate if someone explains in detail what Batch Interface is and how it's different from Command Line Interface?

# Answer
> 1 votes
In the olden days, you wrote up a sequence of operations to be executed (typically on punched cards, a *job*), and handed them to the operator to be loaded. The operating system took such a batch of commands to execute off it's input queue, ran them until the end (or something failed), and took the next one. Output was collected (probably printed out) to return to you.

If the above is what is meant, the crucial difference is that in batch processing you get (perhaps the next day) the feedback that the job failed because of a syntax error or some equally irritating glitch. With a command line interface you run one command, can check it's output or correct the command before entering the next one.

---
Tags: operating-systems
---


# Question
Title: efficiently minimizing quasiconvex function
The problem is as follows: given black box access to a strictly quasiconvex (or unimodal) function $f$ on an interval, say \[0, 1\], query $f$ repeatedly at various points to find a subinterval containing the minimum. After $n$ queries to $f$, if the interval's length is reduced by a factor of $t$, the algorithm's *score* is $\sqrt\[n\]{t}$, which is the amortized factor by which each query to $f$ reduces the length of the interval.

For example, standard ternary search starts with $f(0)$ and $f(1)$, additionally queries $f(\frac{1}{3})$ and $f(\frac{2}{3})$, and obtains a subinterval with size $\frac{2}{3}$. It then iterates and each subsequent iteration starts with $f$ evaluated at the endpoints of the subinterval and reduces the subinterval's length by a factor of $\frac{2}{3}$. Thus the score is $\sqrt{\frac{2}{3}}$.

A better ternary search instead queries at $\frac{1}{2}-\varepsilon$ and $\frac{1}{2}+\varepsilon$ and iterates for a score of $\sqrt{\frac{1}{2}+\varepsilon}$.

An even better algorithm is "pentanary search", starting with $f(0)$, $f(\frac{1}{2})$, and $f(1)$ and querying $f(\frac{1}{4})$ and $f(\frac{3}{4})$ to obtain a subinterval that is the first, middle, or last half of $\[0, 1\]$. It then iterates. The key is that 3 points from each iteration can be used in the next. Thus the score is $\sqrt{\frac{1}{2}}$.

The best I know of, "golden search", starts with $f(0)$, $f(1)$, and either $f(1-\frac{1}{\phi})$ or $f(\frac{1}{\phi})$, querying for the other of those two, where $\phi$ is the golden ratio. The subinterval is either $\[0, \frac{1}{\phi}\]$ or $\[1-\frac{1}{\phi}, 1\]$ and 3 values from the previous iteration can be reused, achieving a score of $\frac{1}{\phi}$.

Can we do better than "golden search"? Do we know the optimal score for this problem?

# Answer
> 2 votes
Avriel and Wilde, in their article Optimality proof for the symmetric Fibonacci search technique, showed that Fibonacci search is optimal in the following sense: if you want to bracket the minimum in an interval of length $\delta$ using at most $k$ evaluations, then Fibonacci search maximizes the length of your initial interval.

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


# Question
Title: Extracting a spanning tree from a directed acyclic graph with minimum total distance between terminal nodes
I have a directed acyclic graph that has uniform edge weights. I would like to extract from this graph a spanning tree (an arborescence) with the property that the total distance between all pairs of leaf nodes (the sum of combined distances from each pair's nearest common ancestor) is minimized.

What I'm ultimately trying to accomplish is to find the best way of ordering the leaf nodes in such a way that the most closely related nodes are closest to each other in the list. If I can find the spanning tree as described, I can easily order the leaf nodes in the way I need.

Can anyone point me to a solution to this problem other than just brute force optimization?

Note that the tree that I seek does not need to span all nodes in the graph, only all leaf nodes and the root node. Also I'm willing to adopt a solution that is not globally optimal if it avoids the need for a brute force search. At the moment I'm investigating an approach involving searching and pruning paths beginning at the leaf nodes.

# Answer
> 1 votes
Your problem is similar to the directed Steiner tree problem. In this problem we are given a directed graph, a set of terminal vertices and a specified root. The goal is to find a minimum cost tree that connects all terminal vertices to the root.

This is not exactly what you are asking for, but perhaps a solution to such a problem (or a suitable variant) is good enough.

---
Tags: algorithms, graphs, dag
---


# Question
Title: k-disjoint pair paths where any source can pair with any sink
I have a question regarding a problem I'm working on.

The problem is given an MxN grid with k sources and sinks, find non intersecting paths (vertex disjoint) such that all sources are paired with a sink. Each source must be paired to a single sink, and each sink must be paired to a single source, however all of the sources are compatible with all of the sinks. This could be imagined as k identical locks and k identical keys, all that matters is that its possible to move the keys into locks without having paths that intersect. By contrast in the original problem, sink Si must be paired with source Di and this is an input parameter of the problem.

The underlying problem is NP-Hard but according to a vague comment I found, with the given restriction it can be solved in polynomial time. Unfortunately I can't find any relevant literature that could help.

https://stackoverflow.com/questions/19404033/all-pairs-maximally-disjoint-paths-algorithm/19411277#19411277

If anyone could point me towards proofs or papers that discuss this problem I would appreciate it.

# Answer
> 3 votes
Your link refers to *edge*-disjoint paths -- i.e., vertices can visited by multiple paths, but no edge can be visited by multiple paths. It sounds like you want *vertex*-disjoint paths -- is that right? Please edit to clarify.

Both problems can be solved in polynomial time with a Maximum Flow algorithm.

For *edge*-disjoint paths, put unit-capacity bidirectional edges (i.e., one edge in each direction) between every pair of adjacent vertices; make a super-source $s$, with unit-capacity out-edges to each of the $k$ sources, and a super-sink $t$, with unit-capacity in-edges from each of the $k$ sinks. The capacity constraints ensure that no edge is used by more than one path.

For *vertex*-disjoint paths, do the same -- but then replace every vertex $v$ with two vertices, $v\_-$ and $v\_+$, with all of $v$'s in-edges incident on $v\_-$ and all of $v$'s out-edges incident on $v\_+$, and add a single directed edge of unit capacity from $v\_-$ to $v\_+$.

---
Tags: algorithms, graphs
---


# Question
Title: Helping prove this notation for Big-O(n!)
Hello, I was wondering if anyone can help me prove the right part of this double equation. I know the left one is possible due to`log(n!) = Θ(nlogn)`. Any help is much appreciated.

# Answer
> 2 votes
Remember that $\Theta(5n \log n^5) = \Theta(n \log n)$, since constant factors don't matter.

Then $\Theta(n \log n) = \Omega(n \log n)$, by the definition of big theta.

$\Omega(n \log n) = \Omega(n)$, because log is monotonic increasing (so we can remove it and still have a valid lower bound).

Finally, $\Omega(n) = \Omega(n^{2/3})$, by the properties of power functions.

---
Tags: time-complexity, big-o-notation
---


# Question
Title: How can i solve this problem using recursion?
```
I have already solve this problem using forloop.
Given an nxn matrix A. Here n is number of row and column. Write a recursive function to find the sum of the diagonal elements of A.
Example:
  3  2 1
  6  3 4
  9 8  3
Output 9

#include<stdio.h>

void main()
{
    int mat[12][12];
    int i,j,row,col,sum=0;
    printf("Enter the number of rows and columns for 1st matrix\n");
    scanf("%d%d",&row,&col);
    printf("Enter the elements of the matrix\n");
    for(i=0;i<row;i++)
    {
        for(j=0;j<col;j++)
        {
            scanf("%d",&mat[i][j]);
        }
    }

    printf("The matrix\n");
    for(i=0;i<row;i++)
    {
        for(j=0;j<col;j++)
        {
            printf("%d\t",mat[i][j]);
        }
        printf("\n");
    }
    //To add diagonal elements
    for(i=0;i<row;i++)
    {
        for(j=0;j<col;j++)
        {
            if(i==j)
            {
                sum=sum+mat[i][j];
            }
        }
    }

    printf("The sum of diagonal elements of a square matrix = %d\n",sum);
}

```

# Answer
I'm going to assume you're asking for an algorithm, since coding questions are generally off-topic here (you might want to try StackOverflow instead).

Remember that the diagonal elements of a matrix $M$ are $M\_{ii}$ for all $i$. This makes the algorithm very similar to summing a list (i.e. taking the sum of $A\_i$ for all $i$).

A recursive algorithm for summing a list would look something like this, in pseudocode:

```
function ListSum(A):
    n ← A.length
    if n = 0: return 0
    else: return A[1] + ListSum(A[2..n])

```

Can you see how this could be adapted to your matrix problem?
> 1 votes

---
Tags: programming-languages, recursion, functional-programming, matrix
---


title: Composition of compostion as a functor

text:
# Question
Title: Composition of compostion as a functor
"Composition of Composition" (i.e., `(.) . (.)`) in Haskell), has type `(a -> b) -> (c -> d -> a) -> c -> d -> b`. Apparently, this is an instance of `fmap`, i.e. a functor between two categories.

The question is: what is the domain and the codomain of this functor? How do we interpret this functor in terms of functional programming?

# Answer
> 1 votes
Consider

```
(.) :: (a -> b) -> (d -> a) -> d -> b

```

is the `fmap` for functor $F\_d\colon \mathfrak{C} \rightarrow d/\mathfrak{C}$ from category of types $\mathfrak{C}$ to its coslice category $d/\mathfrak{C}$ on object $d$. Similarly,

```
(.) :: ((d -> a) -> d -> b) -> (c -> d -> a) -> c -> d -> b

```

is considered the `fmap` for functor $G\_c\colon d/\mathfrak{C} \rightarrow c/\big(d/\mathfrak{C}\big)$.

These two functor can be composed to get $G\_c \circ F\_d\colon \mathfrak{C} \rightarrow c/\big(d/\mathfrak{C}\big)$. Like all compositions of two functors, the `fmap` of the composed functor is the composition of `fmap` its two functor operands. In this case, the `fmap` of $G\_c \circ F\_d$ is

```
(.) . (.) :: (a -> b) -> (c -> d -> a) -> c -> d -> b

```

as in the opening question.

---
Tags: programming-languages, type-theory, functional-programming, category-theory
---


# Question
Title: How to find the best exploration parameter in a Monte Carlo tree search?
I've developed a Monte Carlo tree search algorithm in checkers.

Here is my question. What should be the value of $C$, the exploration parameter in the following formula described in *Monte Carlo Tree Search (MCTS)*?

$$ S\_i=x\_i+C\sqrt{\frac{\ln (t)}{n\_i}}$$

General consensus is that a value of $\sqrt 2$ should be used, but when I use a value of 10 it works, which save me a lot of time.

So, how can I find the best value for $C$, that best suits my problem?

# Answer
The value of $C = \sqrt 2$ was shown to ensure the asymptotic optimality when rewards are in the $\[0,1\]$ range (Kocsis, Szepesvári, 2006).

In many games, that reward range is straightforward: maximum and minimum possible scores can be *translated* to `0` and `1` (`0` could mean a loss and `1` a win).

The accuracy of this *squashing* seems to have a minimal impact (e.g. Using Domain Knowledge to Improve Monte-Carlo Tree Search Performance in Parameterized Poker Squares \- Robert Arrington, Clay Langley, and Steven Bogaerts - 2016).

Unfortunately squashing isn't always possible.

With rewards outside the $\[0, 1\]$ range and/or for fine-tuning the Cross Entropy Method works quite well.
> 3 votes

# Answer
You can go with whatever the literature recommends is a reasonable value without knowing any specifics of your problem. Otherwise, it is perfectly possible (and even to be expected) that a good value of $C$ will depend not only on your problem, but on the details of your instances.

In general with all (meta)heuristics, a good choice of parameters comes down to experimentation.
> 1 votes

---
Tags: algorithms, machine-learning, artificial-intelligence, monte-carlo
---


title: On $L^* - \{\epsilon\} = L^+$

text:
# Question
Title: On $L^* - \{\epsilon\} = L^+$
> $\Sigma^\* - \\{\epsilon\\} = \Sigma^+$
>
> $L^\* - \\{\epsilon\\} = L^+$
>
> Which of the above is always true?

I was following a discussion on a site and I came across this question. Some fellow scholars claimed that the second statement is not always true. The answer they provided is this:

> $S\_1$: $Σ^\* – \\{ϵ\\} = Σ^+$: TRUE // Always true, definition of $Σ^+$
>
> $S\_2$: $L^\* – \\{ϵ\\} = L^+$: FALSE // May or may not be true
>
> False when $ϵ$ belongs to $L$, then $L^+$ and $L^\*$ will both contain $ϵ$.
>
> PS: In $S\_2$, it depends purely on the given language.

But I have this doubt:

How can $L^+$ contain $ϵ$? we obtain $L^+$ by deleting $ϵ$ from $L^\*$, and in $L^\*$ of the language where $L=\\{ϵ\\}$, $L^\*$ will only contain $ϵ$, so if we remove $ϵ$ from it, then the language should become $\emptyset$, which is nothing but $L^+$ here. So shouldn't the second statement also be true?

Say $L^+ = \\{ϵ,ϵϵ,ϵϵϵ,\dots\\}$.

Now an important point. Note that we say **Set of all strings**, now in set theory duplicates are not allowed, moreover $ϵ= ϵϵ =ϵϵϵ =\dots$. They are all just the same. So $L^∗$ should be only $\\{ϵ\\}$, rather than $\\{ϵ,ϵ,ϵϵ,ϵϵϵ,\dots\\}$, right?

# Answer
You got the definition of $L^+$ wrong. It is *not* $L^\* \setminus \\{\epsilon\\}$. Rather, it is $$ L^+ = \bigcup\_{n=1}^\* L^n. $$ You can check that $\epsilon \in L^+$ iff $\epsilon \in L$. Therefore:

* If $\epsilon \notin L$ then $L^+ = L^\*\setminus\\{\epsilon\\}$.
* If $\epsilon \in L$ then $L^+ = L^\*$.
> 5 votes

---
Tags: automata, equality
---


# Question
Title: Smallest segment after whose removal all elements are distinct
I am interested in the following problem:

> We are given an array of integers and we need to find the **size** of smallest subsegment such that after removing it all elements in the array are distinct.

How to solve this problem using binary search in $O(n\log n)$? I tried to read various submissions which use binary search, for example this one, but I couldn't understand them.

My attempt - I solved this problem in $O(n^2\log n)$ using brute force, but I want to know how to apply binary search to solve this problem in $O(n\log n)$.

# Answer
The idea is that you can check whether the answer is at most some value $m$ in time $O(n)$. Applying binary search on $m$, you obtain an $O(n\log n)$ solution.

How do you check whether the answer is at most $m$ in time $O(n)$? The idea is to slide a window of length $m$ across your array. If at some point all elements outside the window are distinct, then we are done.

How do we implement this sliding algorithm? Let $A$ be the original array. We initialize an array $M$ which contains the histogram of the elements in $A\_{m+1},\ldots,A\_n$, as well as the number of distinct elements $x$. If $x = n-m$ then we are done. Otherwise, we modify $M$ to contain the histogram of $A\_1,A\_{m+2},\ldots,A\_n$:

* We remove one copy of the element $A\_{m+1}$ from $M$. If the new count of this element is $0$, then we decrease $x$.
* We add one copy of the element $A\_1$ to $M$. If the new count of this element is $1$, then we increase $x$.

In this way, we can update $M$ in time $O(1)$ per shift.

The solution you link to does all this, apart from maintaining $x$; this is done automatically by the C++ map data structure.

Another point is the time complexity of this solution, which might depend on your exact computation model.
> 0 votes

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


title: heap data structure complexity

text:
# Question
Title: heap data structure complexity
I'm trying to count running time of build heap in heap sort algorithm

```
BUILD-HEAP(A)
heapsize := size(A);
  for i := floor(heapsize/2) downto 1
    do HEAPIFY(A, i);
  end for
END

```

image by HostMath

```
 suppose this is the tree

   4    .. height2
  / \
 2   6  .. height 1
/\   /\
1 3 5 7  .. height 0

```

what I understand here $O(h)$ means worst case for heapify for each node, so height=ln n if the node is in the root for example to heapify node 2,1,3 it takes $ln\_2 3 =1.5$ the height of root node 2 is 1, so the call to HEAPIFY is $ln\_2 n=height = O(h)$

im not sure about this $\frac{n}{2^{h+1}}$ , is the number of nodes for any given height , suppose height is 1 and sum of nodes is 3 such as 2,1,3, so $\frac{n}{2^{h+1}}= \frac{3}{2^{0+1}}=1.5=2$ , when height is 0 there is at most two nodes. am i correct?

suppose given height is 0 so it is the last layer, then when sum of nodes is 7 , $\frac{n}{2^{h+1}}$ =$\frac{n}{2^{0+1}}$=$\frac{7}{2}=3.5=4?$ -\> {1,3,5,7} if the root is 4

the summation is lg n because it sum the total height when it do heapify?

and last is to count the big-oh, BUILD HEAPIFY will call HEAPIFY $\frac{n}{2}$ times, and each will be $ln\_2 n$ = height of the root, so $O(\frac{n}{2} * ln\_2 n)$ ?

please correct me if i am wrong thanks!

https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/ this is the reference i used, and also i read about this in CLRS book

# Answer
Even if i don't really understand your point, i'm try to figure out an intuitive proof for building heap time complexity, starting from a simple recursive algorithm for building heap.

You have a collection of **n** unsorted element, called **A**, you want from this collection build a **heap**(in your case a min-heap because you are mantaining the minimum of collection in the root).

So modelling the heap you want to create like a binary tree, it must shows some property like:

1. **complete**: the tree is "fullfilled" until second-last level and the leaves are "compatted" on the left.
2. **logarithmic height**: if the number in the heap is **n** then the height is O(logn) (you can proof this starting from the first property)
3. **order relation between nodes**: in particular, if v is father of w in the tree then $$ value(v)\<= value(w) $$

Now think A as an unsorted binary tree you can recursively construct an heap follows this step:

1. Make recursive call on the left sub-tree
2. Make recursive call on the right sub-tree
3. Call **heapify** on the root of the current tree

**heapify**

Heapify on a node **v** simply compare v with it sons, and exchange v with the lowest son if it is less than v. Do this repeatedly until exists a son of v that have less value.

**heapify complexity**

So in heapify you make, at most, as many exchanges as high as the tree is, and since the only operation you perform is compare with the son(at most 2) for each level

=\> time complexity is O(logn) for the 2nd property.

now for compute the overall complexity you can set a recursion function considering the worst case in wich A is a **perfect** binary tree (complete and with last level fullfilled).

So let's assume A is a perfect binary tree, the recursion function is:

$$ T(n) = T((n-1)/2) + O(log(n)) $$

because in each recursion step you consider half-part of the tree and exclude the root, and in each step with n as parameter you pay $$ O(log(n))$$ for heapify.

So by **Master theorem** (https://en.wikipedia.org/wiki/Master\_theorem\_(analysis\_of\_algorithms))

$$T(n) = O(n) $$

so you can deduce that building an heap from an unsorted collection of value is **linear** in the number of element in the collection.

Know this maybe don't answer your question but i hope can help!
> 1 votes

---
Tags: complexity-theory, data-structures, time-complexity, heaps, big-o-notation
---


# Question
Title: How to find the smallest of the maximum edges of all paths between two nodes in a graph
Say I have an undirected weighted graph G = (V, E), and I have two vertices s and t. Now there may be a number of paths between s and t, and each path has an edge that has the maximum weight in that path. Out of all these maximum weight edges of all the possible paths, how do I find the smallest one most efficiently?

I suppose I could use a modified Dijkstra's algorithm to find all the shortest paths first, while keep record (like an array) of the maximum weight edges of all possible shortest paths, then maybe use linear time selection to find the smallest one. In this case I think I would have a running time of O((|V| + |E|) log|V|). Is this correct and is there a faster way?

Could I use Kruskal's or Prim's algorithm to find the MST of the graph, and then look at all the edges between s and t in the MST to find the largest one? I am not sure if this is correct at all.

# Answer
> 3 votes
In biref, you can just replace addition function with max function everywhere in the typical shortest path algorithm and it will work because they 'behave' the same way and that the algorithm only ever require the weight (together with the aggregation function) to have that 'behaviour'.

More specifically about that required 'behaviour' of weight. The algorithm only require weight to be any type $\mathbb{W}$ with 'ordered monoid' structure, i.e., comes associated with an addition function $$+\colon \mathbb{W} \times \mathbb{W} \rightarrow \mathbb{W}$$ and with a unique value $$0 \in \mathbb{W}$$ such that it is associative and unital $$(a+b)+c = a+(b+c)$$ $$0+a = a+0 = a$$ and finally with a binary (partial or total) ordering relation on $\mathbb{W}$ satisfying $$x ≤ y \implies z+x ≤ z+y \land x+z ≤ y+z$$ You should check that the correctness proof of the shortest path algorithm only ever utilise these properties.

For fun, you could weight the edges of graph by string, add them using concatenation, have empty string be unit of concatenation, and ordered them lexicographically. Now you can find which path between 2 given points spells out the earliest word in dictionary using shortest path algorithm!

---
Tags: algorithms, graphs
---


# Question
Title: Does Types and Programming Languages use a recursive equation to define a recursive type or its generator?
In *Types and Programming Languages* by Pierce et al:

> **The recursive equation specifying the type of lists of numbers** is similar to the equation specifying the recursive factorial function on page 52:
>
> ```
> factorial = λn. if n=0 then 1 else n * factorial(n-1)
>
> ```
>
> Here, as there, it is convenient to make this equation into a proper deﬁnition by **moving the “loop” over to the right-hand side of the `=`**. We do this by introducing **an explicit recursion operator `µ` for types**:
>
> ```
> NatList = µX. <nil:Unit, cons:{Nat,X}>;
>
> ```
>
> Intuitively, this deﬁnition is read, **“Let `NatList` be the inﬁnite type satisfying the equation `X = <nil:Unit, cons:{Nat,X}>`.”**

I have some questions for understanding it:

1. What does the “loop” mean?
2. Does the recursion operator µ for types play similar role as operator λ for abstractions?
3. Doesn't `NatList` defined by `NatList = µX. <nil:Unit, cons:{Nat,X}>` look more like the generator of the recursive type `X`, i.e. a type mapping so that `X = NatList X`?
4. How can `NatList` as the generator of the recursive type `X` be the inﬁnite type `X` satisfying the equation `X = <nil:Unit, cons:{Nat,X}>`?

Thanks.

# Answer
You've stumbled across the difference between *isorecursive* and *equirecursive* types.

Equi-recursive types say "types are (possibly) infinite trees, and a recursive type is the solution to a recursive equation". Specifically, $\mu x\ldotp T = \[\mu x \ldotp T/x\]T$. These are conceptually simple, but in practice difficult to work with, since deciding whether two types are equal (or worse, subtypes of one another) or not is tricky.

Conversely, isorecursive types say that recursive types are *just syntax*. You are allowed to unroll them according to the equation above, but $\mu x\ldotp T$ and $ \[\mu x \ldotp T/x\]T$ are *fundamentally different types*, and must use the explicit fold and unfold instructions.

If you keep reading Pierce, he will explain this in the book.

Answering your specific questions:

1. The "loop" is that the definition on the RHS or the = is allowed to reference the name defined on the left. This is awkward for theory, because we don't want to treat top-level definitions as special.
2. Yes, $\mu$ is similar to $\lambda$ in the sense that they both bind variables. However, it's different in that there's always a very specific thing that gets plugged in for the bound variable with $\mu$, whereas $\lambda$ is useful precisely because we can plug the variable with anything. Also, the bound variable of $\mu$ denotes a type, whereas with $\lambda$ it denotes a term.
3. Yes, and that's the point of the $\mu$ operator. It says "I am the syntax that takes the generator for a type, and turns it into an actual type you can use like any other type in your program." And it make explicit the role of $X$ in the equation your outline.
4. Again, this is the job of $\mu$ *by definintion*. It is the piece of syntax that says "given the generator, tie the knot and make it an actual type."

The thing is, you can't really understand $\mu$-types on their own. Otherwise it's just syntax. The key is in the type rules for $\mu$ types. For isorecursive types, there are fold and unfold rules that allow us to "run the generator" one step. For equirecursive types, there are special rules in how type equality is determined that allow us to treat $\mu x \ldotp T$ as actually being the solution generated by the recurrence equation. But, these type rules will change depending on the specific language or calculus you're using.
> 2 votes

---
Tags: computability, programming-languages, type-theory, types-and-programming-languages
---


# Question
Title: What algorithms are there for scheduling tasks
The scenario is something like this

* I have tasks that get requested, with a category and a priority
* For simplicity let's assume that rate of incoming tasks and completion is about the same, with some existing backlog of tasks
* Each category of tasks can only be completed at some certain rate
* Completion of tasks is handled out of the system, so we can assume that deciding to take on a certain task is equivalent to completing it

So I want some way of deciding which tasks to complete at a given time, given the existing tasks and their priorities, and the limits on completion within a certain category

One greedy algorithm would be to just organize each category by priority, and then at each decision point take in as many tasks as is allowed by that category's rate, but the problem with this is that if a lot of high priority tasks come in low priority tasks will just sit in the backlog, potentially forever.

I've looked at some scheduling concepts like round robin scheduling and multilevel priority queues, but they don't seem to fit what I want - tasks can't be paused/rescheduled as in round robin, and multi priority queues seems like it'd still have the problem of getting to low priority tasks (could just make the priorities more stratified, but then it's just back to the original problem with deciding how many tasks to take from each queue)

Any advice on what I should look into? Maybe it's a sort of "repeated knapsack" thing?

# Answer
> 2 votes
What you can do is to add another parameter to your tasks, something that I would call dynamic priority delta. Or what is equivalent, you can implement some mechanism to increase or decrease the priority of each task on top of multilevel priority queues.

The basic idea is simple. "A process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form of aging prevents starvation.", reads section 5.3.6 of *Operating Systems Concepts*, seventh edition. For an extreme simple example, you can just increase priority level by one if a task has waited for an hour. Here is more excerpt from that book.

> In general, a multilevel feedback-queue scheduler is defined by the following parameters:
>
> * The number of queues
> * The scheduling algorithm for each queue
> * **The method used to determine when to upgrade a process to a higher- priority queue**
> * **The method used to determine when to demote a process to a lower- priority queue**
> * The method used to determine which queue a process will enter when that process needs service
>
> The definition of a multilevel feedback-queue scheduler makes it the most general CPU-scheduling algorithm. It can be configured to match a specific system under design. Unfortunately, it is also the most complex algorithm, since defining the best scheduler requires some means by which to select values for all the parameters.

Your situation might be even more complex since your task are also labelled with category. Without more information, I cannot advise further into your scheduling algorithm.

I encourage to read chapter "CPU Scheduling" of *Operating System Concepts* by Avi Silberschatz, Peter Baer Galvin and Greg Gagne. For even more content, read chapter "Uniprocessor Scheduling" and "Multiprocessor and Real-Time Scheduling" of *Operating System Internals and Design Principles* by William Stallings. Although they are talking about CPU or processor scheduling, most of the concepts and algorithms are the same as in or can be applied to job/task scheduling. You will find lots of inspirations and ideas and references.

# Answer
> 0 votes
One solution that I've read about, but haven't tried implementing myself as of yet, is to slowly increase the priority of tasks as time goes on. For instance, each time you pop off requests you could update all lower-priority tasks (or after every X requests have been popped off, etc). Thus eventually all tasks will get to execute.

# Answer
> 0 votes
Most every operating system under the sun has it's take on this. Check an operating systems text, they describe some simple variants.

For Linux, the standard is the Completely Fair Scheduler (CFS); but there are others to handle real time tasks.

---
Tags: algorithms, scheduling
---


# Question
Title: NFA to recognize bit strings containing 01111110
Basically, I currently have two ideas but unsure on which is correct for the following question: "The High level data link control protocol (HDLC), is a popular protocol used for point-to-point data communication. In HDLC, data are organised into frames which begin and end with the sequence 01111110. This sequence never occurs within the main body of the frame, only at the beginning and end (in order to avoid confusion).

a.)Design an NFA which recognises the language of binary strings which contain one or more HDLC frames"

My possible solutions:

The next part is to convert to DFA, but I first need to get this part right.

# Answer
Might as well go for a DFA directly.

First, recognize the string `01111110`. If you see something you don't expect, then the information is malformed and you should enter a dead state.

Once you've seen `01111110`, start looking for `01111110` again, but this time, if you see something you don't expect, begin looking for `01111110` again from scratch. Once you see a complete `01111110`, you have consumed an entire frame, and you should be in an accepting state.

Then, from this halting state, we add the same transitions we have on our initial state; i.e., we leave open the possibility that there are additional frames. Here's a transition table corresponding roughly to what I've indicated:

```
  State     Input     New State
  q0        0         q1
  q0        1         dead
  q1        0         dead
  q1        1         q2
  q2        0         dead
  q2        1         q3
  q3        0         dead
  q3        1         q4
  q4        0         dead
  q4        1         q5
  q5        0         dead
  q5        1         q6
  q6        0         dead
  q6        1         q7
  q7        0         q8
  q7        1         dead
  // we've seen the leading 01111110
  q8        0         q9
  q8        1         q8
  q9        0         q9
  q9        1         q10
  q10       0         q9
  q10       1         q11
  q11       0         q9
  q11       1         q12
  q12       0         q9
  q12       1         q13
  q13       0         q9
  q13       1         q14
  q14       0         q9
  q14       1         q15
  q15       0         q16
  q15       1         q8
  // we have now seen the trailing 01111110, a whole frame
  // q16 is the only accepting state.
  q16       0         q2
  q16       1         dead

```

Naturally, you'll want to check that very carefully. If the goal is outputting the message in between the leading and trailing patterns, you might need some extra states to remember input symbols that may or may not be part of the trailing pattern; but for accepting input which consists of a finite number of valid frames, this (or something close to it, if I've made a silly blunder) should be enough.
> 1 votes

# Answer
The previous answers seem to be incorrect. Let $A = \\{0,1\\}$. Since you don't want to have the pattern $0110$ as a strict internal factor, the language you are looking can be written as $01111110 A^\* 01111110 \setminus 0A^\* 01111110 A^\*0$. You may use the question Designing a regular expression for the set of all binary that contain strings without a particular sub string (i.e. 110) but you will still have to work a little bit to find the minimal DFA of this language, which has 24 states. The unique final state is 24.

```
   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0  2  0  0  0  0  0  0  9 17 17 17 17 17 17  0 17 17 17 17 17 17 17 24  0
1  0  3  4  5  6  7  8  0 10 11 12 13 14 15 16 16 18 19 20 21 22 23 16  0

```
> 0 votes

# Answer
"Containing 01111110" is easily handled directly with an DFA. Start with something that just recognizes that string; check for each state what you should do to loop back if mismatch (i.e., after 1 if a premature 0 shows up, you have to start over looking for a 1; if the second 0 isn't there, start over at the beginning). After you got your target, anything goes.
> 0 votes

# Answer
Express the language as a regular expression. Then there is a completely rote method to convert the regular expression to an NFA. I found a particularly good explanation at http://www.csee.umbc.edu/~squire/cs451\_l6.html:

While you can represent r+ as rr*, you can actually add a seventh rule that is just like the r* rule, but leaves out that bottom $\epsilon$ transition:

You can clean up the final NFA at the end by removing any state that has only a single output transition that is also an $\epsilon$ transition. You remove the source state of the $\epsilon$ transition, and merge all of the inputs of the source state into the destination state of the $\epsilon$ transition. This often applies to parts of the NFA created by the concatenation rule (rule 5) and the union rule (rule 4).

I think you will get something similar to your second picture, except note that your original problem called for an NFA that recognizes one *or more* frames.
> -2 votes

# Answer
I think the regular expression `[01]*01111110[01]*01111110[01]*` will do. It is not identifying the individual frames, but that wasn't asked either. So this expression is making sure that the string of bits starts with the proper marker and ends with it. Anything can go in between. You can use the method of Wandering Logic to make an NFA out of it. The DFA will be a bit more complicated, but 20 minutes should suffice.
> -2 votes

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


# Question
Title: Detecting rotational symmetries of spatial structures
I have a spatial graph-like structure. The structure consists of vertices in the 3D space and connecting edges. Are there any algorithms available that would identify the rotational symmetries of these structures? In particular, I'm interested in all the rotational axis along which I can rotate the structure to overlap itself, as well as the degree of rotation. For example, an equilateral triangle (3 vertices + 3 edges) would have one rotational axis perpendicular to its plane, with a degree of 3 and 3 others in its plane, with a degree of 2 each. The closest I could find are molecular packages identifying the symmetry groups of molecular structures. I would prefer not to go that far as I'm only interested in rotational symmetries and not entire group theory description of structures.

# Answer
Here is one approach to identify all rotational symmetries of the graph:

Pick any three vertices, $v\_1,\dots,v\_3$. Loop over all possible combinations of three vertices $w\_1,\dots,w\_3$. For each such combination, find the unique rotation that maps $v\_1 \mapsto w\_1,\dots,v\_3 \mapsto w\_3$, then check whether this is a rotational symmetry of the entire graph (by mapping the entire graph and seeing whether the mapped graph coincides with the original graph).

The worst-case running time will be something like $O(n^4)$, where $n$ is the number of vertices in the graph. In practice I expect it to be typically more like $O(n^3)$, as most candidate rotations can be immediately rejected by testing a few vertices.

To identify the unique rotation that maps $v\_1 \mapsto w\_1,\dots,v\_3 \mapsto w\_3$, given $v\_1,\dots,v\_3,w\_1,\dots,w\_3$, see https://math.stackexchange.com/q/3341635/14578.
> 1 votes

---
Tags: algorithms, graphs, graphics, group-theory, polygons
---


# Question
Title: Solving recurrence relation where the $f(n)$ has some constant factor $k$ where $0 < k < 1$
I am trying to see if a recurrence relation where $f(n)$ has some constant factor $k$, e.g. $f(n)=kn$ where $0 \< k \< 1$, is $O(n)$. I am reaching a different result depending which route I take. Given the following recurrence relation:

$$T(n)=2T(\frac{n}{2})+f(n)$$ $$T(n)=2T(\frac{n}{2})+kn$$ Since $0 \< k \< 1$, we can represent $kn=n^c$, where $0 \< c \< 1$

This falls under the case 1 of the Master Theorem, because $a=2, b=2$, and therefore $log\_b a = log\_2 2 = 1 \> c$.

It's $O(n)$.

But if I try to unfold the recurrence: $$\begin{split}T(n) & = 2T(\frac{n}{2})+kn \\ & = 4T(\frac{n}{4})+2kn \\ & = 8T(\frac{n}{8})+3kn \\ & = ... \\ & = 2^cT(\frac{n}{2^c})+ckn \\ \end{split}$$

When $\frac{n}{2^c}=1$, $n=2^c$, then $log\_2 n = c$.

So now it's $T(n) = nT(1) + kn log\_2 n$, which is $O(n log\_2 n)$. Now I am confused.

# Answer
> 2 votes
The error is where you claim that $kn=n^c$ where $0\<c\<1$. This is not correct. Even when $k\<1$, it is still the case that $kn=\Theta(n)$; it is not $O(n^c)$ for any $c\<1$. (Check the definition of big-O notation.)

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


# Question
Title: Rice Theorem - Problem to understand and apply it
I have struggle to understand the Rice Theorem.

My understanding of Rice Theorem:

The purpose of this Theorem is to proof that some given language L is undecidable iff the language has a non-trivial propertie.

So, if I want to apply this Theorem I have to show that the following conditions are satisfied:

1) There are two TM's which have the same language and they are either both in the language $L(M\_1)=L(M\_2)$ or neither is in L ($M\_1 \wedge M\_2$ are no specific (picked) machines).

2) I have to show that there exists two specific TM's: $M\_1'$ which has the property and $M\_2'$ which doesn't have the property.

Is this correct?

Perhaps someone can give an example, so that I know how to apply the rice theorem.

What's about the language: $L=${$\<M\>$|$\emptyset$ $\subseteq$ $L(M)$}

For the first condition:

There are two turing-machine's which have the same language and doesn't accept the language L.

For the second condition:

* $M\_1$ is the turing-machine that accepts all, and...
* $M\_2$ is the turing-machine that rejects all.

So both conditions are true which implies I can apply the Rice Theorem?

Thank's for your help.

# Answer
From Wikipedia:

> Let S be a set of languages that is nontrivial, meaning
>
> 1. there exists a Turing machine that recognizes a language in S,
> 2. there exists a Turing machine that recognizes a language not in S.
>
> Then it is undecidable to determine whether the language recognized by an arbitrary Turing machine lies in S.

It's the language (determined by the TM) that has the property, not the TM itself. Your first condition is not needed at all, and the second condition should state "$L(M\_1')$ has the property, and $L(M\_2')$ does not."

An example of application of Rice's Theorem might be the following statement. The set $$S = \\{\<M\> : \varepsilon \in L(M)\\}$$ is undecidable. The corresponding TMs might be $M\_1$ which only accepts $\varepsilon$ and $M\_2$ which doesn't accept any words.

Your example is not correct since the property is trivial. $\emptyset \subseteq A$ for any set $A$, even an empty set.
> 1 votes

---
Tags: turing-machines, undecidability, rice-theorem
---


# Question
Title: How to prove by contradiction that every nonempty hereditary language contains the empty string?
A language L is called hereditary if it has the following property:

For every nonempty string x in L, there is a character in x which can be deleted from x to give another string in L.

Prove by contradiction that every nonempty hereditary language contains the empty string.

Here's my attempt:

To prove by contradiction, we assume that for every nonempty string x in L, there is no character in x which can be deleted from x to give another string in L.

This means that if a character in x is deleted an empty string is left. Since an empty string is also a string, every nonempty hereditary language contains the empty string.

I'm not exactly sure how to proof by contradiction. Can someone help review this?

# Answer
> 0 votes
Let L be a nonempty hereditary language. Let x be one of the shortest strings in L. x exists because L is not empty.

Removing any character from x would produce a string not in L, since x is one of the shortest strings. Because L is hereditary, we can remove a character from x giving another string in L, unless x is the empty string. Therefore x is the empty string. Therefore L contains the empty string.

If you insist on proof by contradiction: Let L be a nonempty hereditary language not containing the empty string, and let x be one of the shortest strings in L. x is not the empty string since L doesn't contain the empty string. Therefore there is a character in x which can be removed, giving a string y in L.

But y is shorter than x, therefore x is not the shortest string in L.

---
Tags: proof-techniques, check-my-answer
---


# Question
Title: Which algorithm for predicting the next word(s) based on previous words, given a sentence?
I want to input some words, and out comes the next word(s). Neural nets are really hot at the moment, and I'm afraid of throwing a neural net at something, when one is not really needed. Or... maybe it is needed?

My current options are:

* Predict next word(s) using N-grams
* Predict next word(s) using a neural net

There are quite a number of Github repositories that does this using neural nets, and a few that does it with N-grams. Are there any clear advantages to choosing the neural net approach?

# Answer
You can use anything you like. Right now neural networks are the state of the art: they produce the best predictions. But you could also use HMMs, or n-grams, or other methods; they just will be lower quality than a state-of-the-art neural network.
> 1 votes

---
Tags: neural-networks, natural-language-processing
---