# Question
Title: Why not $O(n^{\log_ba})$ for case 1 of the Master Theorem instead of $O(n^{(\log_ba) - \epsilon})$?
Someone who was explaining to me the master theorem said that for the case 1, we compare the $n^{\log\_b(a)}$ and $f(n)$. If the growth rate of $n^{\log\_b(a)}$ is greater than the growth rate of $f(n)$ then we subtract an epsilon to have this equality: $$f(n) = O(n^{(\log\_ba) - \epsilon})$$

My question is, doesn't the notation $O$ say that $n^{\log\_ba}$ is the upper bound of the $f(n)$? So why don't we just write $$f(n) = O(n^{\log\_ba})$$

# Answer
Good question.

Suppose we have a positive function $T(n)$ such that

$$T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)$$

with $a \geq 1, b \> 1$. You are referring to case $1$ of the master theorem:

$\qquad$ If $f \in O( n^{\log\_b (a) - \epsilon})$ for some $\epsilon \> 0$, then $T \in \Theta\left( n^{\log\_b a} \right)$.

(There are various versions of the master theorem. There is not much variation on the case $1$, though.)

#### Why don't we just write $f(n) = O(n^{\log\_ba})$ as the antecedent for case $1$?

Because we cannot.

For example, consider $T(n)=2T(\frac n2)+n$.
So $a=2$, $b=2$, $\log\_ba=1$, $f(n)=n=O(n^1)$. However, $T(n)\not\in\Theta(n^1)$.

In fact, $T(n)\in \Theta(n\log n)$. This $T(n)$ belongs to the situation with $a=b=2, k=0$ of the case $2$ of the master theorem:

$\qquad$ If $f \in \Theta( n^{\log\_b a} \log^{k} n)$ for some $k \geq 0$, then $T(n)\in \Theta( n^{\log\_b a} \log^{k+1} n)$.

#### Can we just write $f(n)=o(n^{\log\_ba})$ as the antecedent for case $1$?

No, we cannot either.

For example, consider $T(n)=2T(\frac n2)+n/\log n$.
So $a=2$, $b=2$, $\log\_ba=1$, $f(n)=n/\log n\in o(n^1)$. However, $T(n)\not\in\Theta(n^1)$.

In fact, applying Akra–Bazzi method, we have $T(n)\in \Theta(n\log\log n)$. See here for an easy explanation why $T(n)\in \Theta(n\log\log n)$.

#### So, $O(n^{(\log\_ba) - \epsilon})$ for some $\epsilon\>0$.

"Case $1$ of the master theorem only applies if $f(n)$ is significantly (i.e. by an order of $n^ε$ for some $\epsilon\>0$) smaller than $n^{\log\_ba}$", as ttnick remarked.
> 3 votes

---
Tags: big-o-notation, master-theorem
---


# Question
Title: If the two generals problem is unsolvable how can we human beings agree on things?
If the two generals problem is unsolvable how can we human beings agree on things?

I mean, we communicate everyday and have the same limitations as any communication problem handled by computer science. Why doesn't it affect us?

# Answer
I disagree with other answers that the communication channel needs to be modelled differently. Malice is irrelevant, simple lost messages with any non-zero probability are sufficient to create the two generals problem. e-mail and IM, for example, have a low but not zero chance of dropping messages. Phone calls can suffer interference, so as with the two generals problem you need to somehow confirm whether the other person heard what you said, ad infinitum. And yet I frequently use these channels to make agreements with other people.

What the insoluble "two generals" problem fails to solve, is to get *guaranteed* common knowledge. In real life we don't require formal common knowledge in order to proceed. Therefore the goal in most practical situations needs to be described differently from the goal in the two generals problem.

We settle for agreement being "sufficiently likely". I might not be willing to attack unless I'm *certain* you will attack, but I'm willing to walk to the coffee shop to meet you provided that the probability of a communications failure isn't grossly higher than the probability of you failing to arrive due to traffic. Unlike the generals, I'll take a chance on you meeting me.

If you've ever had someone explain something three times to you in different ways when you got it the first time, or ever had someone ask you to confirm something that you've already confirmed twice, then it's because you reached your threshold of "sufficiently likely" before they reached theirs.

Take your pick of psychology, philosophy, or evolutionary biology as the correct realm in which to look for an answer to the next question, why we don't really need a full guarantee of common knowledge :-)

It also relates back to practical problems in computing. For example when we use a single-error-correcting code to "validate" that a symbol in a message has arrived correctly, all we're doing is accepting that the probability of a double-error is negligible for the time being. Then later in the protocol we might have a CRC, to further reduce the probability of undetected error. None of this solves the two generals problem, but it is sufficient for me, my bank and a merchant all to "agree" that a credit card transaction has occurred, with a small probability that we disagree.
> 35 votes

# Answer
Central (pun intended) to the Two Generals problem is a malicious enemy in between. Although this models an unreliable channel, it models it in a way that we normally don't encounter. In the problem, the messages may pass through enemy hands and there's no time constraints, verification, encryption or anything else I haven't thought of.

When we communicate in practice, firstly the channels we use are not expected to be unreliable in this manner. Channels can be noisy, sure, but that's different to being malicious. The probability that a channel that is noisy at the bit level can randomly produced not only a valid message that satisfies whatever error correcting code we're using, but is also valid in that it makes sense to the receiver is very low. We can also use things like public key cryptography to encrypt and/or sign messages, making it harder again to fake a real message. Thirdly a significant chunk of our communication is time sensitive - we actually talk to people so there's no delay in response, in which case we will have to be satisfied that the person we're talking to is the person we're meant to be talking to.

In the majority of cases, we just assume that there's no significant source of error in the messages, and we get away with it. We can imagine a scenario where there really is a malicious man-in-the-middle corrupting the channel, but we come across a couple of things; the public key crypto is still effective, but more importantly the effort and power needed to accurately corrupt a significant enough portion of communication is far beyond what is feasible. If it were not, military signals intelligence would be far more effective than it is (not that it's not effective, it would just be better).

Note that although I have touched on computer/machine mediated communication mostly, the same arguments can be made for interpersonal communication - the sources of noise can't typically fake an entire message, we have correction systems for those that introduce random, low-level noise, and the effort is just not worth it in almost every case for there to be a sufficiently resourced and motivated malicious attacker.
> 17 votes

# Answer
The "unsolvability" of the "Two Generals" problem (or called "Coordinated Attack" problem) is restricted to its context, i.e., in a totally asynchronous distributed system with unreliable, untrusted communication channels. In our daily life, people can "tolerate" such bad situations.

In the book *Reasoning about Knowledge*; Section 6.1, the authors comment that

> The fact that coordinated attack implies common knowledge depends on our requirement that the coordinated attack must be ***simultaneous***. **In practice**, simultaneity might be too strong a requirement. A protocol that guarantees that the generals attack within a short time of each other may be quite satisfactory.

He further comments that

> Nevertheless, even such weaker forms of coordination are unattainable if ***communication is unreliable***.

In our daily life, people can tolerate (and are tolerating) short delays and unreliable channels (as elaborated by @Luke Mathieson). (If you go deeper and ask "how" and "why", then it is probably out of the scope of computer science.)
> 17 votes

# Answer
Because we don't need guaranteed *assurance* that something *will* happen when we have sufficient *experience* that tells us what is *likely* to happen. For example, let's say that a friend wants to meet up with me. He emails me the time and place, and I respond back with "Sounds great, see you then." I don't need any more information to proceed with meeting him at the specified place and time. Just because I couldn't *guarantee* that he got my response isn't enough to sway me from acting on my assumptions. My experience tells me that email is fairly reliable, and that if for some reason he didn't get my response, he'll email me again. My experience tells me not to worry about the corner case of my response being silently discarded, and all followup messages from him also being silently discarded. That combination of events just doesn't happen often enough to significantly interfere with my ability to meet people.

If those corner cases (or other issues) did start to happen more often, that would change my *experience*, and then I'd consider changing my strategy. For example, I might call the person instead of emailing them. Or I might use a calendar website. Or some other option.

As applied to interpersonal communication, I find that the technical issues of the two-generals problem aren't hugely problematic on their own, but can magnify other problems. If I email someone a work request and I don't get a response from them in a reasonable amount of time, what do I do? How long should I hold off before sending a followup message? If I do send a followup message, will they see it as a friendly reminder, or are they going to feel irritated? How should I word the followup message so as not to come across as too presumptuous (because if the network actually dropped the previous message, then this is the first they're hearing from me)?

The nature of these questions all depends on the people and the context involved. There are no guaranteed answers. But again, we don't need guarantees to be successful. All we need are things like introspection, empathy, and the ability to learn from experience. We can discover and develop our own unique strategies -- which may well differ from others -- that enable us to become better communicators over time.
> 5 votes

# Answer
You can never go from an uncertainty to a certainty. The two generals problem is one where the only action that can be taken (sending a message) is an uncertain one.

If we changed the problems to have certainties then it's solvable. Like if general A had a portal that with 100% certainty a messenger can walk through and be right next to general B instantly. In this scenario, general A sends exactly one message and then rides out to battle at the specified time. No further message sending is required by either of them.

If you're standing right next to another human it's just the simple equivalent of having the portal.
> 0 votes

# Answer
Can you give me the exact value of pi in decimal notation? We humans round-off and approximate when we know the exact value is unsolvable.
> -1 votes

# Answer
The proof only says that it is impossible to design a protocol that reliably solves the problem (i.e. perfectly in every instance).

It doesn't say it is impossible to design a protocol that mostly solves the problem. Humans, being bayesian in nature, are quite good at designing protocols that solve a given problem with some degree of quality and/or some degree of success that is satisfactory in terms of gains and losses in the long run.
> -1 votes

---
Tags: computer-networks, communication-protocols
---


# Question
Title: Two Generals problem - what if we set boundary conditions, and then layer redundant messages once they've been met?
apologies if this is in wrong place (very new to CS). I know there must be some flaw in my reasoning here, but I can't quite see it. Here's how I've stated the problem.

---

There are two generals, A and B. Messages start from A with a request M and B replies with an agreement N. Thereafter, the generals must exchange acknowledgements A*n* and B*n* of message reception. That is, after receiving N, A will send A1; upon receiving A1, B will send B1; and so on.

M reads:

> Attack at time X. Once I receive your reply, we will begin exchanging the acknowledgments A*n* and B*n*. As soon as we both know that you have received A1, and we both know that I have received B1, we will consider the plan finalized and proceed.

* M goes through. N is sent, agreeing to M.
* A1 is sent, acknowledging M and N. B1 is sent, acknowledging M, N and A1.
* A2 is sent, acknowledging M, N, A1 and B1. B2 is sent, acknowledging M, N, A1, B1, and A2.
* So on for A*n* and B*n*

By the time B*n* is sent, B knows the following: **I've told A that I received A1 n times, and I *know* he heard me n-1 times. So he knows I received A1.** At this same time, A knows the following: **I've told B that I received B1 n-1 times, and I *know* he heard me n-2 times. So he knows I received B1.** Recall that the boundary conditions for the attack were: **As soon as we both know that you have received A1, and we both know that I have received B1, we will consider the plan finalized and proceed.**

If we set n = 3, these conditions seem to be met. If we set n arbitrarily higher than that, it works.

---

As I understand it, the point of the Two Generals problem is that is that neither party is willing to proceed while the chance of the other proceeding is less than 100%. I also know that classically, each additional message increases the chance of a general proceeding asymptotically towards 100%. But if we set boundary conditions such as these, and then add some layers of redundant messages, there is some *shared knowledge* between the two generals, and the possibility that either one will not attack falls to 0? Have we not established that both generals *know* that the attack criteria have been met with 100% certainty?

I know this problem's unsolvable, so I must've made a mistake somewhere. I just can't see it.

# Answer
> 2 votes
Realize first that if General $X$ doesn't receive message $X\_k$, then General $X$ *must assume* that General $Y$ didn't receive message $Y\_{k-1}$.

---

Suppose that General $B$ does not receive the final message $B\_n$. An important question is: *Why is that?*

In General $B$s mind, General $A$ didn't necessarily receive $A\_{n-1}$. And *that* would be bad.

Suppose in this hypothetical scenario that $B$ *believes* that $A$ didn't receive $A\_{n-1}$. That *could be* due to $B$ not receiving $B\_{n-2}$. But why didn't $B$ in this scenario receive $B\_{n-2}$. Well, possibly because $A$ didn't receive $A\_{n-3}$.

That means that if $B$ doesn't receive $B\_n$, $B$ must assume that $A$ assumes that $B$ assumes that $A$ didn't receive $A\_{n-3}$ ... ad infinitum.

The problem here is that after $A$ and $B$ split, there is no more new *common knowledge*. A nice way of modeling this situation is with the use of possible worlds.

# Answer
> 1 votes
Whenever you think you have solved the two general problems, there is only 1 thing you need to do to find why your solution is wrong.

Take every step s\_1...s\_n of your algorithm and treat it as the final step before a permanent network failure. Does a general end up dead if any step s\_i is the final step before total network failure? Then you haven't solved it.

> If we set n = 3, these conditions seem to be met.

If I understand you correctly, that means once B receives A3 he will be confident enough to attack? Okay then let's say B gets A3 and then a permanent network failure occurs. He sends his B3 messages out but A never gets it and never gets confident enough to attack. General B rides out to his death alone.

If you try to argue that general A should also be confident enough at this point to attack because he has already received B2 then all you've done is move the problem backwards a bit. If A gets B2 then a permanent network failure occurs then A will ride out to his death alone.

# Answer
> 0 votes
An even simpler method is to consider that:

* For the first few messages, both generals know to refrain.
* For the later messages, both generals know to attack.
* Between these two states, each general will get a message and move from the first state to the second.

But if communication is cut off when only one of these two critical messages has been received, one general now knows not to attack and the other knows to attack, and everyone dies.

There is no known method by which the generals can know that they are in this situation.

---
Tags: algorithms
---


# Question
Title: Given x <= y, find a sum adding to y such that all elements are <= x and decreasing and the final element is maximised
Given $x \leq y$, find a sum $y\_1+y\_2+...+y\_n$ where $y\_i \leq x$ and $y\_{i-1} \geq y\_i$ for $1 \leq i \leq n$ and $y\_n$ is maximised.

For example, given $x = 5$ and $y=17$, an optimal solution would be $17=5+4+4+4$

# Answer
Notice that you can restrict yourself to solutions such that $y\_1 - y\_n \le 1$ (otherwise you can iteratively move one unit from a term with value $y\_1$ to a term with value $y\_n$).

Suppose now that you choose to break the sum into $n$ terms (which might not be feasible). Then the only such solution uses $y \bmod n$ terms of value $\lceil \frac{y}{n} \rceil$ and the remaining terms (at least one) of value $\lfloor \frac{y}{n} \rfloor$.

Then the problem boils down to maximizing $\lfloor \frac{y}{n} \rfloor$, and hence minimizing $n$, with the constraint $\lceil \frac{y}{n} \rceil \le x$. Therefore we can pick $n = \lceil \frac{y}{x} \rceil$.
> 0 votes

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: Nearest line-segment to a query point or conversely
I have a set of line segments (say 1000 of them) and a query point. I want to find the segment which is the closest in the Euclidean sense (if the point does not project on the segment I accept two options: 1) just ignore the segment - infinite distance - or 2) consider the distance to the closest endpoint). Preprocessing of the segment set is allowed.

In the case of nearest points, a 2D-tree is a good fit. Is there a good generalization to line segments ? Or another classical data structure ? (Voronoï and point-location is complex to implement, I'd prefer something more tractable, even if not perfectly efficient.)

Alternatively, I am interested by a solution of the converse problem: finding the closest point to a given query line segment.

# Answer
One approach is to compute the Voronoi diagram of these line segments. Here are two papers that consider this problem:

A robust and efficient implementation for the segment Voronoi diagram. Menelaos I. Karavelas. International symposium on Voronoi diagrams in science and engineering, 2004.

VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments. Martin Held. Computational Geometry 18(2), 2001.
> 0 votes

# Answer
I think the easiest is to put the segments into an index (quadtree, R-Tree, BVH, ...), they will typically be represented by their bounding box. Then you can use nearest neighbor search with a custom distance function that calculates the distance to the actual segment represented by the bounding box. Depending on how the index supports distance functions (do you have access to the associated data, i.e. which diagonal represents the segment?), you may need to filter the results manually.

You can also avoid a custom filter by querying for all boxes that overlap with you query point and then manually check all overlapping boxes to find the one that represents the segment closest to your point.

If your segments are very long (i.e. they are likely to overlap) you can do some preprocessing and split up long segments into shorter ones until a search point will typically overlap with only very few bounding boxes.
> 0 votes

# Answer
Consider Morton Encoding (https://en.wikipedia.org/wiki/Z-order\_curve). It's pretty easy to implement, simpler than most two-dimensional indexes, and works pretty well.

What does "closest segment" mean? Are you just looking for the single segment endpoint closest to your target point? Or do both ends of the segment matter?
> -1 votes

---
Tags: computational-geometry, nearest-neighbour
---


# Question
Title: Prove if $L = \{0^m1^n \mid m \neq n\}$ is regular or not
I am trying to show whether this language is regular or not:

$$L = \\{0^m1^n \mid m \neq n\\}$$

Since I cannot create or think of an automaton that recognizes $L$, I am suspecting that $L$ is not regular. From the book I am using, it seems I can use the pumping lemma, I have done this:

Let $p$ be the pumping lemma constant, and let $w=0^p1^{p+1}$

In this case $$|w|=2p + 1\geq p$$

We can divide $w$ into $xyz$, where $x=0^{p-1}$, $y=0$, $z=^{p+1}$, then $|y|\geq 1$

If L was regular, then $\forall k \geq 0, xy^kz \in L$. Let choose $k=2$, then:

$$xyyz=0^{p-1}001^{p+1}=0^{p+1}1^{p+1}$$

Here is where I am stuck, how do I prove that $L$ is not regular?

Another question, pumping lemma applies only to infinite languages?

# Answer
> 7 votes
You don't need to invoke the PL directly here. Instead, we'll do a proof by contradiction. Suppose $L$ was regular, then, since regular languages are closed under complement, $\overline{L}$ is regular (where the overbar represents complement), and since regular languages are closed under intersection, $\overline{L}\cap 0^\*1^\*$ would be regular (where the regular expression denotes the language $0^\*1^\*=\\{0^n1^m\mid n,m\ge 0\\}$), but $\overline{L}\cap0^\*1^\*=\\{0^n1^n\mid n\ge 0\\}$, which you likely know is not regular, establishing the contradiction we needed. Thus your language isn't regular.

In answer to your other question, the PL generally applies only to infinite languages since you don't know what the PL integer $p$ is, so absent other information, you need an infinite language to be sure that there is *some* string of length $\ge p$ in the language, regardless of how large $p$ is.

# Answer
> 7 votes
It's not so evident, but *you can also apply the PL directly*:

* let $p$ be the pumping length
* pick $w = 0^p 1^{p + p!}$

Clearly $w \in L$

The pumping lemma says that $w = xyz$ with $|xy| \leq p, |y| \geq 1$, so we have that $y$ must be "made of" $0$s; suppose that $y = 0^a\\;, 0\< a \leq p$; then by the PL we have:

$$xyz = 0^{p-a} 0^{ai} 1^{p +p!} \in L\quad \text{ for all } i \geq 0$$

It's enough to pick: $i = (1+p!/a)$ and you get:

$$xyz = 0^{p-a} 0^{a(1+p!/a)} 1^{p +p!} = 0^{p-a} 0^a 0^{a (p! /a) }1 ^{p + p!} = 0^{p+p!}1^{p+p!} \notin L$$

(just note that $p! / a$ is an integer because $0\<a\leq p$)

# Answer
> 2 votes
The pumping lemma applies to *all* languages. Let $L$ be a finite language. The pumping lemma says that, for some $p$, every string in $L$ that is longer than $p$ can be written as blah, blah, blah. Since $L$ is finite, every string in it has length at most $\ell$ for some $\ell$. So just take $p\>\ell$ and the requirements of the pumping lemma are vacuous: $L$ has no strings of length greater than $p$, so there are no counterexamples to the claim that every string of length greater than $p$ can be written as blah, blah, blah.

# Answer
> 2 votes
Other answers have already mentioned about pumping lemma and Myhill-Nerode theorem. Through which you could prove that a DFA does not exists to accept the given language, hence it can't be regular.

One quicker way (not actually a formal proof) to check whether a language is regular or not is to see if your DFA has to count infinitely in order to recognise the language, then it is not regular.

For $L=\\{0^m1^n \mid m \ne n\\}$, the DFA has to count the number of 0s and then count the number of 1s. If they are equal then reject it otherwise accept the string. Here with no upper bound on m, it could be infinitely large and the DFA can't keep track of m. So it is not a regular language.

Is $L=\\{0^m1^n \mid m \ne n, 0 \le m \le 2\\}$ regular? Here $m$ has an upper bound. The DFA could count up to $m$ and then see if it is equal to $n$ or not. We could have a DFA accepting for regular expression $(1^+)+(0+011^+)+(00+001+00111^+)$

Is $L=\\{0^m1^n \mid m \ge 0, n \ge 0\\}$ regular? Here the DFA does not even need to count anything. The regex would be $(0^\*1^\*)$

# Answer
> 1 votes
You can also use Myhill–Nerode theory.

Consider a DFA accepting your language, and let $q\_i$ be the state that the DFA is in after reading $0^i$. I claim that $q\_i \neq q\_j$ whenever $i \neq j$, which is impossible since a DFA only has finitely many states. Indeed, if $q\_i$ were equal to $q\_j$, consider the state that the DFA is in when starting at $q\_i$ and reading $1^i$. Since $0^i1^i \notin L$, it should be a rejecting state, but since $0^j1^i \in L$, it should be an accepting state – and we have reached a contradiction, showing that the assumption $q\_i = q\_j$ must be wrong.

# Answer
> 0 votes
You have almost proved the language is not regular using Pumping Lemma,

In the last step where you pump up the string you get

$$xy^2z = xyyz=0^{p-1}001^{p+1}$$ $$=0^{p+1}1^{p+1}$$

which does not belong to the language L, this contradicts your assumption that the language is regular, So the Given language is not regular.

---
Tags: computability, automata, finite-automata, pumping-lemma
---


# Question
Title: Expected runtime of recursive algorithm with optional part
I have a randomized recursive algorithm which expected running time is $T(n)$. In particular, the recursion looks like this: $$ T(n) \leq \mathcal cn + R ,$$ where $R$ is a recursive term that depends on $T(n-i)$ for some values of $i$, and $c$ is some constant. I want to add a procedure to this algorithm that samples the input data and performs some computation with it. There are two outcomes to this procedure: if it is positive, then let the algorithm proceed as normal; if it is negative, then sample and perform the computation again. Suppose that the added procedure runs in at most $d\cdot g(n)$ time for some constant $d$.

How can I write the recursion for the expected running time for this new algorithm?

# Answer
If the probability for resampling is $p(n)$, then the running time satisfies $$ T(n) \leq Cn + R + p(n) \cdot d g(n). $$
> 0 votes

---
Tags: algorithm-analysis, recursion, randomized-algorithms
---


# Question
Title: Compressed string lookup by name or ordinal
I have a large list of strings with associated values. I need to do a fast lookup into the list by the string prefix, but also by the string's ordinal within the list. For example,

```
string,value,ordinal
--------------------
alice, 10, 0
bob,   99, 1
carol, 32, 2

search_by_prefix("bo") -> [("bob", 99),]
search_by_ordinal(2) -> ("carol", 32)

```

I'm looking for a good compressed data structure.

A simple sorted string table (SST) does the job, but it's not well-compressed. You can do key prefix compression, but it doesn't buy you much.

I'd prefer to do a finite state transducer (FST) because it's very compact and lookups are fast. The problem is that I can't find a simple explanation of how to construct one, and it also isn't clear how to do a by-ordinal lookup.

Suggestions?

This data structure can be read-only. No need for inserts or deletes.

# Answer
A reasonable approach is to build two data structures, one optimized for prefix-based search and one optimized for ordinal-based lookup.

For prefix-based search, a trie is the natural data structure. It might not be very compressed, either, due to number of pointers it requires. A Patricia tree may be somewhat better but it still requires many pointers. It's possible you might be able to come up with a way to lay out nodes in memory so that most pointers can be replaced by small indices.

For ordinal-based search, a simple array of pointers should suffice.
> 1 votes

---
Tags: finite-automata, data-compression, string-matching
---


# Question
Title: Counting integers $n \leq x$ with a given prime signature
Given is a prime signature $S$ and an integer $x$. The task is to count how many integers $n$ exist such that $n \leq x$, and if $n = p\_1^{k\_1}p\_2^{k\_2}p\_3^{k\_3}p\_4^{k\_4}...$ then $S = (k\_1,k\_2,k\_3,...)$. Let $C(S,x)$ be that count.

For example, if $S = (3,1,1)$ and $x=1000$ then there are $21$ such integers, being $$120, 168, 264, 280, 312, 408, 440, 456, 520, 552, 616, 680, 696, 728, 744, 760, 888, 920, 945, 952, 984$$

And so $C\big((3,1,1),1000\big )=21$. Notice that the order matters, so $270=2\cdot 3^3\cdot 5$ does not appear in this specific list. It would appear for $S=(1,3,1)$ for large enough $x$. The signature consists only of positive integers, and the primes are sorted in increasing order, $p\_i\<p\_j$ for all $i\<j$.

Currently I have thought of just $1$ approach for this:

1. First, use recursion to generate such integers, keeping track of the currently generated integer $n$, and the index of the largest prime used, $i$.
2. Once the last part of $S$ is reached, call it $k\_m$, count the number of primes smaller than $\sqrt\[k\_m\]{\frac xn}$ and make sure only primes larger than $p\_i$ are included. That is, add $\pi \Big(\sqrt\[k\_m\]{\frac xn}\Big) - \pi(p\_i)=\pi \Big(\sqrt\[k\_m\]{\frac xn}\Big) - i$ to the total count.

It may be assumed the prime counting function implementation used for this algorithm is very efficient. Still, I have to compute $C(S,x)$ for thousands of signatures, and for $x=10^{12}$, so either my implementation of the above algorithm is lacking, or there is simply a better way to compute $C(S,x)$.

This is part of a recreational maths problem, but is in itself a nice problem, so any approaches to calculate the function efficiently are welcome.

# Answer
> 2 votes
Here is a complicated approach that might offer a modest improvement for values of $x$ of the size mentioned in your comment, when you want to compute $C(S,x)$ for many different $S$ and the same $x$:

---

Let me focus first on the case where $S$ has the form $S=(\cdots,1,1)$.

Let $f(u,v)$ be the number of integers of the form $p\_1 p\_2$ satisfying $u \le p\_1\<p\_2$ and $p\_1 p\_2 \le v$. We can precompute a table that lets us compute $f(u,v)$ very rapidly whenever $u\le 10^3$, $v \le 10^6$.

A naive approach is to store $f(u,v)$ for all $u,v$ satisfying $u \le 10^3$, $v \le 10^6$. This can be stored in an array with $10^3 \times 10^6 = 10^9$ elements. We can fill in the array using the recurrence $f(u,v) = f(u+1,v)$ if $u$ is not prime, or $f(u,v) = f(u+1,v) + 1$ if $u$ is prime and $v/u$ is prime and $v\>u^2$. In particular, for each $v$, start by computing $f(1000,v)$, then $f(999,v)$, then $f(998,v)$, etc.

A more efficient approach is to store $f(u,v)$ only when $u \le 10^3$ is prime and $v \le 10^6$ is a product of two different primes. If we build a list of all products of two different primes $\le 10^6$, given any $u,v$, we can find the smallest prime $u'\ge u$ and the largest product of two primes $v' \ge v$ (via binary search in the list) and finally look up the value $f(u',v')$, using the fact that $f(u,v)=f(u',v')$. It will be possible to fill in the lookup table with a few million operations.

Once we've built the lookup table, it is now possible to offer an improved algorithm for computing $C(S,x)$ whenever $S$ has the form $S=(\cdots,1,1)$. In particular, use the same algorithm as in the question, but once the last two parts of $S$ are reached, if $n \ge x/10^6$ and $q\le 10^3$ where $q$ was the prime used in the third-to-last part, then compute $f(q,x/n)$, add $f(q,x/n)$ to the total count, and end the recursion. (If $n\<10/x^6$, continue on with the recursion as in your algorithm.)

You can optimize the parameters $10^3,10^6$ above to speed the algorithm up, based on the amount of storage available and the distribution of sizes of $x/n$. (I doubt $10^3,10^6$ are optimal; I chose them more or less arbitrarily to try to make the approach easy to understand, not because I believe those are the best parameters.)

---

Now, if you have multiple signatures all of the form $S=(\cdots,1,1)$ varying in their first parts, then you can reuse the same table $f$ for all of them.

In a similar way you can build another table for all signatures of the form $S=(\cdots,1,2)$ or $S=(\cdots,2,1)$ or any other common suffix.

---

You can also take this a step further, by building an analogous lookup table to help with all $S$ where $S=(\cdots,1,1,1)$.

Let $g(t,v)$ be the number of integers of the form $p\_1p\_2p\_3$ satisfying $t \le p\_1 \<p\_2\<p\_3$ and $p\_1p\_2p\_3 \le v$. We'll precompute a lookup table that stores $g(t,v)$ for all $t,v$ where $t \le 10^3$, $v \le 10^9$, where $t$ is prime and $v$ is a product of three distinct primes.

To fill in the lookup table, we'll use the fact that $g(t,v) = g(t^\*,v) + f(t^\*,v/t^\*)$, where $t^\*$ is the smallest prime with $t^\*\>t$. In this way, for each $v$, we can fill in $g(t,v)$ in the order $g(997,v), g(991,v), g(983,v), g(977,v), \dots$. The lookup table will have fewer than $10^9$ entries and can be built with less than $10^9$ steps, so it is probably feasible to build it in a few seconds if implemented appropriately.

Once we've built the lookup table, we can use it to improve the algorithm for computing $C(S,x)$ whenever $S$ has the form $S=(\cdots,1,1,1)$. In particular, use the same algorithm as above, but once the last three parts of $S$ are reached, if $n \ge x/10^9$ and $q\le 10^3$ where $q$ was the prime used in the fourth-to-last recursion, then compute $g(q,x/n)$, add $f(q,x/n)$ to the total count, and end the recursion. (Otherwise, continue the algorithm as above).

Now you can reuse the $g$ lookup table for all $S$ that have the form $S=(\cdots,1,1,1)$.

You can optimize the parameters $10^3,10^9$ for performance, and do something similar for any other common suffix.

---
Tags: algorithms, time-complexity, optimization, discrete-mathematics, primes
---


# Question
Title: Complexity of multiplying bivariate polynomials of degree n
Let $P(X,Y)$ and $Q(X,Y)$ be two bivariate polynomials of degree at most $n$. Using $O(n^2)$ FFTs, we can compute the product $PQ$ in time $O(n^3\log n)$.

**Q:** Is there a faster algorithm to compute $PQ$?

# Answer
It suffices to describe how to evaluate $P(\omega^u,\omega^v)$ at the roots of unity. Suppose $P(X,Y)=\sum\_{i,j} a\_{i,j} X^i Y^j$. Let

$$F\_{b,c}(X,Y) = \sum\_{i,j} a\_{2i+b,2j+c} X^i Y^j$$

where the sum is over all $i,j$ with $i\le n/2, j \le n/2$. Then

$$P(X,Y) = F\_{0,0}(X^2, Y^2) + Y F\_{0,1}(X^2, Y^2) + X F\_{1,0}(X^2, Y^2) + XY F\_{1,1}(X^2, Y^2).$$

Therefore you can evaluate $P(\omega^u,\omega^v)$ at the $n^2 $ roots of unity by evaluating each $F\_{b,c}(\omega^{2u},\omega^{2v})$ at the $(n/2)^2$ roots of unity. This leads to a recursive algorithm whose running time is given by

$$T(n) = 4 T(n/2) + O(n^2),$$

which has the solution $T(n) = O(n^2 \log n)$. This immediately leads to an algorithm to compute the product $P(X,Y) Q(X,Y)$, analogous to the standard algorithm for (univariate) polynomial multiplication with DFTs, by evaluating at the roots of unity, multiplying pointwise, and then applying the inverse DFT. I'll let you fill in the details from here.
> 4 votes

---
Tags: polynomials, multiplication
---


# Question
Title: How does instruction set architecture affects clock rate?
According to the computer organization and design RISC-V 2nd edition 2020, section 1.5, the following table states that ISA affects clock rate.

| Hardware or software component | Affects what? | How? |
| --- | --- | --- |
| Algorith | instruction count, CPI | The algorithm determines the number of source program instructions executed and hence the number of processor instructions executed. The algorithm may also affect the CPI, by favoring slower or faster instructions. For example, if the algorithm uses more divides, it will tend to have a higher CPI. |
| Programming language | Instruction count, CPI | The programming language certainly affects the instruction count, since statements in the language are translated to processor instructions, which determine instruction count. The language may also affect the CPI because of its features; for example, a language with heavy support for data abstraction (e.g., Java) will require indirect calls, which will use higher CPI instructions. |
| Compiler | Instruction count, CPI | The efficiency of the compiler affects both the instruction count and average cycles per instruction, since the compiler determines the translation of the source language instructions into computer instructions. The compiler's role can be very complex and affect the CPI in varied ways. |
| Instruction set | Instruction count, clock rate, CPI | The instruction set architecture affects all three aspects of CPU performance, since it affects the instructions needed for a function, the cost in cycles of each instruction, and the overall clock rate of the processor. |

Since there can be many implementations of the same ISA with different clock rates, I wonder how ISA can affect the clock rate of a CPU.

# Answer
> 1 votes
The affect of the ISA on clock rate and CPI is not simple. The amount of work needed to decode the instruction and perform the operation can vary among instructions. If more work (that can not be done in parallel) needs to be done to process an instruction, then either the pipeline must be made longer or the pipeline stages must be longer. Consider the following two examples.

First compare two ISAs that are identical except that one (B) uses a denser instruction encoding that would add 5% to the length of a decode stage in a classic five stage pipeline (compared to the less densely encoded ISA A). One choice for ISA B would be to lengthen all pipeline stages by 5% (i.e., expand all stages equally); this choice might simplify the partitioning of work when reusing an existing design for the other ISA and the extra time in non-decode stages need not be wasted — e.g., increasing cache associativity could use more time in cache access pipeline stages, the ALU might use a smaller and/or more energy efficient adder, relaxing timing margins in most of the design might increase yield. This choice would increase the cycle time by 5%. The effect on CPI would depend on how the extra cycle time was used; increasing cache associativity would tend to reduce misses and therefore CPI (fewer cycles waiting for memory), extra fetch time might be used to improve branch prediction (reducing CPI), and even the lengthening of cycle time itself will tend to reduce CPI (e.g., memory latency and bandwidth can be less tied to the processor clock frequency).

Another choice would be to rebalance the pipeline while keeping the same pipeline depth. In theory, this could reduce the cycle time cost down to 1%, but the work of processing an instruction is not friendly to arbitrary division; some timing inefficiency will be introduced and area/power costs will likely increase (e.g., the placement of pipeline stage edges can affect the amount of data that must be latched). This would ideally only increase cycle time by 1% and have no effect on CPI.

Another choice would be to completely rework the pipeline and increase its length. If the fetch and decode stages were increased to three stages to form a six stage pipeline. If the cycle time was kept constant, this would provide roughly extra 95% of a cycle for additional work. The extra time might be used to access a larger instruction cache, perform decode-time optimizations such as instruction fusion (requiring wider fetch and/or instruction buffering), or do other useful work. Increasing the pipeline depth would increase the branch misprediction cost, increasing CPI, but uses of the extra time such as a larger instruction cache would tend to reduce CPI. If the total work was kept constant, increasing the number of stages by 20% would increase the frequency by something less than 20%; however, such encounters the difficulty of arbitrarily dividing work.

(Yet another choice might be to precode instructions, moving some decode work to when the instruction cache is filled on a miss. The same in-memory capacity instruction cache would be physically larger, possibly increasing cycle time. Alternatively the physical cache size might be kept more-or-less constant, possibly even with similar typical capacity in the number of instructions; however, this would be difficult to acheive as the number of wordlines in an SRAM array wants to be a power of two. Since instruction cache misses are slow anyway and less common than instruction fetches, moving decode delay could be helpful even if only part of the delay was shifted and there was some inefficiency of work due to the division.)

Since a denser instruction encoding would effectively increase instruction cache size in terms of the number of instructions, this could decrease CPI by decreasing instruction cache misses.

For a second example, consider a RISC-like ISA and a similar ISA but with load-and-operate instructions. Since some of the instructions are more complex, it would be expected that decoding an instruction would require more work with implications similar to those in the previous example. (Adding load-and-operate instructions would also tend to increase code density.) Ignoring any extra work for instruction decoding, implementing load-op instructions by simply cracking such into a load µop and an operate µop would be problematic for the classic five stage pipeline: the operate µop would have to stall during the MEMory pipeline stage whereas a compiler might often be able to place an instruction independent of the load immediately after the load. If 36% of instructions in the evaluation are loads and half of those are replaced by load-op instructions and the compile can fill half of the slots after loads, using load-op instructions would add cycles equal to 9% of the instruction count (half of the loads (18% of instructions) would be converted to load-ops and half of those (9% of instructions) would have an extra unused cycle compared with the RISC. (The CPI would obvious look much worse since the number of instructions is reduced. A 9% increase in cycle count with only 82% of the instructions would give almost 33% higher CPI.)

More sophisticated pipeline control would allow an instruction immediately following a load-op to execute while waiting for the data from the load µop of the previous instruction, making this equivalent to the RISC design. However, the more sophisticated control would likely increase cycle time. (The original MIPS R2000 did not use interlocking in order to increase frequency; to do this while supporting load-op instructions might require a skewed pipeline where loads are started at what would be the execute stage and computations would be executed two stages later when loaded data would be available — this would require a separate functional unit for calculating addresses.)

A load-op instruction avoids using one register for a temporary, so such would slightly reduce register pressure and spill-fill overhead (instruction count). A load-op instruction would also provide limited instruction buffering which might hide a single cycle/instruction hiccup in the front-end, but more general buffering could be implemented independent of the ISA. If the critical paths/loops in the design happened not to be lengthened by more complex decode and more sophisticated pipeline control (i.e., cycle time was not increased), the free temporary register could give a slight performance advantage.

These two examples hint at some of the tradeoffs even for a simple short-pipeline scalar implementation. Increasing pipeline depth decreases efficiency; not only is latch overhead more-or-less constant but equally dividing work is more difficult with shorter pipeline stages and some work is not entirely independent (branch prediction removes the control dependency but is not completely accurate). Where a pipeline stage ends also influences area and power costs (e.g., how many bits need to be latched); increasing area will tend to increase communication latency, which tends to decrease exploitable parallelism.

Instruction decode complexity and work complexity will also impact the difficulty of increasing execution width. Fixed length instructions make parsing the instruction stream into individual instructions trivial at the cost of code density and/or instruction count. Easily determining the instruction length — such as the S/360's use of two bits in a fixed position to indicate which of three instruction lengths applied — can be a reasonable compromise. Caching instruction boundary determinations using one bit per instruction parcel (length unit) to indicate a whether a parcel is at the boundary or not can reduce the parsing latency for later parsings.

More variable execution latencies also increase the complexity of result forwarding. Operations which take only a little more time than a simple addition introduce the choice of increasing the cycle time to allow such to be done in a single cycle or performing them in two cycles (ignoring possibilities such as delivering partial results as they are needed — e.g., width pipelining/staggered ALU —, doing more work to produce a result faster, or cracking the operation into single-cycle µops). Increasing cycle time has obvious drawbacks, but increasing the latency of *some* operations increases complexity. In a two-wide 5-stage design, a two-cycle operation would not need to add a forwarding path if it used the load execution pipeline (both loads and such higher latency operations would take two cycles so no new forwarding paths would be required), but if such operations were expected to be common limiting them to single wide execution and only when a load is not being issued may be undesirable. Increasing the number of forwarding paths increases the difficulty of meeting high frequency targets.

The ISA does not *determine* the clock rate but influences the tradeoffs involved in achieving a given clock rate. With techniques such as cracking instructions into multiple µops, fusing instructions, idiom recognition (for special handling of special cases), and out-of-order execution an ISA can be translated dynamically to work better with design constraints but such translation is not free.

---
Tags: computer-architecture, cpu, instruction-set
---


# Question
Title: Looking for a dictionary of math/CS notation
There is an at-times dizzying array of symbols used in math and CS papers. Yet many assume basic familiarity that seems rarely taught in one place. I am looking for a dictionary something like the following, especially from a CS perspective.

* It would list all the basic mathematical symbols and give their meanings and examples. It would talk about symbols that are sometimes used in equivalent ways. It would note common beginner mistakes.
* It would talk about the subtleties surrounding different meanings of a single symbol (much like multiple definitions of the same word in a dictionary).
* It would not merely be a very terse description of each symbol, such as one word descriptions like "subset".
* It would show how symbols are sometimes "overloaded". For example, $\binom{x}{y}$ could have $z$ as an integer, but sometimes $z$ can be a set with this notation and it means to choose elements from this set. $\[n\]$ sometimes means a set of integers $1 \ldots n$, or other times its a one-element array.
* It might talk about how to describe all kinds of different "objects" in terms of different symbols or equivalent ways of referring to them (but which are more clear) and the operations possible on those objects. In other words, kind of like an API for math objects.

I.e. it would be also at times a "style manual" for different nuances in how to present mathematical writing. This would be a very helpful resource for anyone writing questions in mathematical stackexchanges, where many questions fail to make sense based on not fitting into tricky mathematical conventions.

Some book introductions have many of these features. however ideally it would be a separate treatment. Also, ideally of course it would be online. There are tables of latex symbols, but they don't really fulfill many of the above criteria.

> Has anyone seen a "dictionary of symbols" that matches these features?

(Alternatively, it seems like an excellent wiki or FAQ project if good references like this don't exist.)

# Answer
> 9 votes
You can use this sheet. It has a lot of handy formulas and some definitions.

You can also use Wikipedia's list of mathematical symbols propsed by Kyle Jones in comments.

There is also Worfram MathWorld which is a great resource, but you need to know what are you looking for.

When it comes to printed resources, each volume of The Art of Computer Programming has a great reference of mathematical notations, especially volume 1.

# Answer
> 4 votes
> To know something's secret name is to steal its power. - Dr. Daniel Jackson

For the times when we can only draw the symbol and want a name.

See: shapecatcher

You draw the symbol and if there is a unicode char for it, it will find it and give you a name. If there are many such as =, it will list many results.

Then it is just a matter of Googling.

Enjoy!

# Answer
> 3 votes
To the other answers' references for mathematical notation and symbols, I would like to add a reference for mathematical use of English words.

The book, A Handbook of Mathematical Discourse is a dictionary of words and phrases used in semi-formal mathematical writing—especially words like "where" and "all" that are used quite differently from non-mathematical writing.

# Answer
> 1 votes
You won't find all of your requirements in one place. As to:

> it would be also at times a "style manual" for different nuances in how to present mathematical writing.

Check out:

***Mathematical Writing***, Issue 14 of MAA notes, *Donald Ervin Knuth, Tracy Larrabee, Paul M. Roberts*

Publisher Mathematical Association of America, 1989 ISBN 161444322X, 9781614443223

---
Tags: terminology, reference-request, education
---


# Question
Title: Does category theory only deal with immutable objects? If so, why?
IIUC, category theory only applies to immutable objects, and mutability is modelled within that using e.g. functors, monads. Is that true? If so, why doesn't category theory include immutability? Has no-one got round to adding that, or is it impossible?

I'm asking because I've never seen category theory applied to, or discussed in the context of, imperative code or languages, and I want to know if it can be.

# Answer
It is not true. The state monad expresses mutable state that can be used in a computation, and that is just one example.

A second example is Frank Oles's PhD thesis, supervised by John Reynolds, where a presheaf model of Algol, a procedural language with mutable variable, is given. This work was subsequently extended and adapted.
> 2 votes

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


# Question
Title: Programming language compiler that will perform the composition of primitive functions with optimization
**Is it possible to create a some programming language compiler that will perform the composition of primitive functions with optimization?**

In fact, the maximum possible optimization in the context of function composition.
In this case, primitive means that the code consists only of while, if, break, continue statements, assignment, standard mathematical operations and functions.

*Example 1*. `x = sqrt(x * x)``x = abs(x)`
*Example 2*. `filter(filter(list, |x| % 2 == 0), |x| > 2)``filter(list, |x| % 2 == 0 && |x| > 2)`. One list traversal instead of two.
*Example 3*.

```
for i in [0:10:1]: # from 0 to 10, step = 1
    first_array[i] = i
for i in [0:10:1]: # from 0 to 10, step = 1
    second_array[i] = first_array[i] + 1
for i in [0:10:2]: # from 0 to 10, step = 2
    third_array[i] = first_array[i] * second_array[i] * input(i)

```

```
for i in [0:10:2]: # from 0 to 10, step = 2
    third_array[i] = i * (i + 1) * input(i)

```

**Update**
The goal is to reduce the memory overhead (in fact, the array ceases to be an array and exactly the elements used in it are used for intended purpose) and time (predictable values are calculated in advance).
Output code must satisfy certain correctness criteria, e.g., must compute some particular function.

There are inputs that limit the optimization. But everything else should be optimized at compile time as much as possible.

# Answer
This is a very broad topic. You are basically asking about program optimization, which is an entire subfield/topic area within compilers. There are dozens of books and research conferences dedicated to the subject. It is a hard problem. Most solutions are focused on a specific subset of the problem or particular special cases.

Much of the work that I have seen has focused on machine language rather than high-level code, perhaps because the semantics and performance model is easier to specify. Much of the work I've seen focuses on time or the size of the code, rather than the runtime memory usage, because runtime memory usage is challenging to automatically reason about, especially without knowing the workload that the code must handle (e.g., the distribution of inputs to the code).

You might be interested in superoptimization, which does a sort of brute-force search over possible programs, program synthesis, which attempts to construct code that achieves a desired function, and automatic loop vectorization, which converts iterative loops to a form that can be implemented more efficiently.
> 2 votes

---
Tags: programming-languages, compilers, program-optimization
---


# Question
Title: What is good algorithm to decode morse code strings?
```
moorse_string[] = {".-",      //  0 = A ('A' = ASCII code 65; 'a' = ASCII code 97)
                       "-...",    //  1 = B
                       "-.-.",    //  2 = C
                       "-..",     //  3 = D
                       ".",       //  4 = E
                       "..-.",    //  5 = F
                       "--.",     //  6 = G
                       "....",    //  7 = H
                       "..",      //  8 = I
                       ".---",    //  9 = J
                       "-.-",     // 10 = K
                       ".-..",    // 11 = L
                       "--",      // 12 = M
                       "-.",      // 13 = N
                       "---",     // 14 = O
                       ".--.",    // 15 = P
                       "--.-",    // 16 = Q
                       ".-.",     // 17 = R
                       "...",     // 18 = S
                       "-",       // 19 = T
                       "..-",     // 20 = U
                       "...-",    // 21 = V
                       ".--",     // 22 = W
                       "-..-",    // 23 = X
                       "-.--",    // 24 = Y
                       "--..",    // 25 = Z
                       "-----",   // 26 = 0 (ASCII code 48)
                       ".----",   // 27 = 1
                       "..---",   // 28 = 2
                       "...--",   // 29 = 3
                       "....-",   // 30 = 4
                       ".....",   // 31 = 5
                       "-....",   // 32 = 6
                       "--...",   // 33 = 7
                       "---..",   // 33 = 8
                       "----.",   // 34 = 9
                       "--..--",  // 36 = , (ASCII code 44)
                       ".-.-.-"   // 37 = . (ASCII code 46)
                      }

```

Only thing I can think of is to match each string of code with the array of strings above until a match is found. I want to think of a better way to decode this without brute force. For example, if I have "..---". This is located at 28 index of the array. and My code now looks from 0 - 28 and finds a match and breaks. Please suggest better ideas thanks.

I want to handle following list of chars only:

and Morse encodings within a word are separated by a single space. Spaces between words and new lines are separated by three spaces.

Answer does not have to be code, but codes are accepted. Answer can be any valid suggestions that explain the logic wholly in words(atleast). I just want to explore different way of thinking. Any answer that is different from what I suggested will be accepted even if it is a worse algorithm. But if there is 2 answers then the more elegant one will be accepted. I am not asking for the solution but ideas. How would you approach the problem? and why? What is the logic that drives the algorithm? If you consider you way better than what I suggested then why?

# Answer
> 0 votes
You could build a tree where each node has a name and two children ("Dot" and "Dash").

For `--.`, you'd:

* Look at the Dash child of the tree's root node.
* Go to its Dash child.
* Then go to that node's Dot child.
* Then take the name of the node "G".

For `--.-`, you'd do the same thing, but instead of taking the "G", you go to "Dash" and then find that it's "Q".

This is basically the way that people process the code and anticipate the target letter while they are listening to it; they get the `--.`, and wait for the next sound to determine whether it is a "G", or perhaps a "Q", "Z", "7", or ",".

# Answer
> 2 votes
What you suggest is already a good method. It is what I would recommend. It is simple and easy to implement. That is a good thing. Generally, those qualities mean that it takes less time for the programmer to implement, and is less likely to have subtle bugs. Normally, as a first starting point, we want to optimize for reducing programmer time, even if it takes the computer a little longer, because the programmer's time is far more expensive than the computer's. Only if the resulting code is too slow do we begin to examine more sophisticated algorithms and data structures.

Here are two pithy quotes I like that capture these sentiments well:

That said, if you want a fancier data structure, a trie would be appropriate. It might yield better performance (or it might not, depending on memory hierarchy and cache effects).

---
Tags: algorithms
---


# Question
Title: Possible to solve a combinatorial game with integer programming?
I recently had the idea that it would be neat if it were possible to make a SAT solver play combinatorial games. To start, I'm trying a relatively simple case of solving single-stack Misère Nim through integer programming: there's a fixed limit $L$ with a set of moves $N$, where a move is added to the state each turn. Each player is trying to avoid making the state equal the limit.

I managed to encode this with integer programming with the following system:

* A move at each time $t$ is either played or not played: $0\leq m\_{n,t}\leq 1$
* A game is either in progress or over: $0\leq p\_t\leq 1$
* The state is between one and the goal: $1\leq s\_t \leq L$
* The game starts at state 1 and is in progress, and ends at limit and not in progress: $s\_0=1, p\_0=1, s\_{final}=L, p\_{final}=0$
* Exactly one move of the possible moves can be played iff the game is in progress: $\sum\_{n\in N}m\_{n,t}=p\_t$
* The game cannot resume once stopped: $p\_t\leq p\_{t-1}$
* The current state is the previous state plus the current move: $s\_t=s\_{t-1}+\sum\_{n\in N}nm\_{n, t}$

I believe this encoding successfully represents the set of legal games, and enables with minimal additions asking questions like "What is the shortest/longest game" and "Is there a legal game with these constraints".

Where I'm struggling is handling adversarial behavior. I'm not sure how to ask questions like "can this player force a win" via integer programming. I suspect it may not be possible since SAT is in NP but many combinatorial games are in EXP, so the language might not be able to express (cleanly) the idea of an optimal sequence of play. But it may be possible that special cases like Nim (definitely not EXP) yield clever solutions. I can't find any literature on this.

Hence the question: **Is it possible to express optimal play for a combinatorial game as integer programming constraints? If so, how?** A general solution for zero-sum combinatorial games is preferred if possible, but even just a solution for the special case of (single-stack) Nim would be interesting.

# Answer
> 1 votes
I believe you can't, for many/most combinatorial games. In particular, I believe optimal play for two-player combinatorial games is often a PSPACE-complete problem (sometimes a EXP-complete problem), while a SAT solver can only express NP problems (and a polynomial-time algorithm equipped with ability to call a SAT solver can only solve problems in $P^{NP}$). Since it is believed that PSPACE is much bigger than NP (or $P^{NP}$), it is unlikely that a SAT solver will be enough to solve all such game problems.

See, e.g., Playing Games with Algorithms: Algorithmic Combinatorial Game Theory, Erik D. Demaine and Robert A. Hearn, Games of No Chance 3, volume 56, pages 3-56, 2009; or David Eppstein's page, or Wikipedia's page (also here and here).

Another way to think about it is that reasoning about adversarial play often involves formulas of the form $\forall x\_1 \exists y\_1 \forall x\_2 \exists y\_2 \forall x\_3 \exists y\_3 \cdots \varphi(x\_1,y\_1,\cdots)$. Here the $x\_1,x\_2,\dots$ variables represent one player's moves, and the $y\_1,y\_2,\dots$ variables represent the other player's moves. In general, such formulas are PSPACE-complete to solve: see TQBF. Therefore, it is unlikely that they can be solved with a SAT solver (or an ILP solver).

---
Tags: satisfiability, integer-programming, game-theory, optimal-strategy
---


# Question
Title: Regular expressions cannot be used to express context free grammars. Is there a similar notation that can?
Regular expressions are a powerful practical tool for string processing. But there are simple examples of useful string processing tasks (like, say, removing brackets from an expression `(E) -> E` when `E` might itself contain brackets) which cannot be represented by a convenient regular expression.

Is there a language of expressions that can be used to conveniently process patterns defined by a context-free grammar?

# Answer
Most domain-specific languages for context-free grammars are some variant of Backus-Naur form (BNF). A number of popular programming languages have BNF modules, like python's `pyparsing` module. They are also a first-class entity in the Raku programming language (a variant/successor to Perl) - see Raku rules. More commonly, you can write BNF grammars for various parser generators and then consume the generated parsers from a language of your choice.
> 1 votes

---
Tags: context-free, regular-expressions
---


# Question
Title: Is there a defined set of steps or principles on how to reduce time complexity of algorithms?
I have been watching some big (Google, Facebook,..) company interview examples and usually when pair programming, they develop the most straightforward algorithm and then the interviewer asks 'could you make it faster (reduce time complexity)'.

I have worked on optimizations of algorithms too and things that immediately spring to head when I optimize is to take out as many nested loops as possible, look for sorted data, change data structures, etc.

Since algorithm optimization is a common thing I was wondering **is there a defined set of steps or principles on how to approach the reduction of time complexity of algorithms?** something akin to SOLID for Object-oriented programming, but for reducing time complexity.

# Answer
> 1 votes
Just something to remember: You said "could you make it faster (time complexity)". What counts in practice is the resources used for practical cases. Reducing the runtime by a factor ten may be extremely valuable, but doesn't reduce time complexity. It is in practice more valuable than reducing time complexity by a factor log log n.

Next thing to remember: In many cases "could you make it faster" has the valid response "Probably, but I wouldn't bother". Making it faster takes time in money. The first step is to figure out whether it's worth the effort. Especially in an interview.

One method that works very well is called "brute force and ignorance". It doesn't care about algorithms, but about making the identical code run faster. Removing all unneeded overhead. Check for cache usage and so on.

And the other method is finding better algorithms. O (n\*n) can often be changed to O (n log n), which is massively better. And with really complicated algorithms, you may find some heuristics that improves it. For example, optimisation algorithms tend to work a lot better if you manage to start with a *good* solution that may be good enough to allow you showing that many other solutions cannot be optimal.

But general principles? No.

# Answer
> 0 votes
There are no defined easy steps you can follow. The principles you mentioned, like using efficient data structures or noticing patterns that can optimized are often the basis for optimizing algorithms, but the number of different techniques is large. Most of the techniques used in interview questions can be found in basic algorithms textbooks like Introduction to Algorithms.

# Answer
> 0 votes
A systematic approach is to start with Brute Force and then Keep thinking what is unnecessary or repeated, try to eliminate those steps... many times it's not so obvious and which is why it is considered a difficult process unless you have solved like hundreds of algorithmic problems ... which is when you clearly see what is unnecessary or repeated that can be eliminated.

---
Tags: algorithms, time-complexity, optimization
---


title: How to use BNF for {a^n b^n | n>0}

text:
# Question
Title: How to use BNF for {a^n b^n | n>0}
so I know that this language is not regular, however, can you still define the language using BNF? This is the problem:

```
{a^n b^n |n>0}

```

# Answer
> 1 votes
This is a classic example of a context-free language. See How to prove that a language is context-free? for how to find the corresponding context-free grammar. Then once you have a context-free grammar, you can write it down in BNF.

---
Tags: regular-languages
---


# Question
Title: Algorithm/heuristic for large tournament matchup pairings
I'm scheduling a large invitational tournament with the following conditions

1. The event takes place over 8 weeks
2. Teams arrive and depart on different dates/times, so each day of the event will have a different number of teams available to play
3. Teams will play only once per day
4. Teams have specific criteria they ask for, which means
    * Some pairs of teams can not play (e.g. teams requested not to play each other)
    * Some pairs would be a better matchup than others (e.g. similar skill level). I can create a score for a matchup based on the two teams' preferences (perhaps on a scale of 1-100).

My desired output would be a set of matchups per day which optimizes for highest combined score of matchups for the entire event. The solution does not have to be optimal, but should be close. This is something I would run only once, so speed is not very important.

What is a good algorithm/heuristic to approach this problem?

# Answer
> 2 votes
A good approach is to use integer linear programming (ILP). This is basically an operations research problem, and ILP is a powerful tool for problems like this.

You can introduce zero-or-one integer variables $x\_{i,j,d}$, with the intended meaning that $x\_{i,j,d}=1$ means that teams $i,j$ play each other on day $d$. Each of your constraints can be expressed using linear inequalities. The objective is a linear function of the variables, i.e., $\sum\_{i,j,d} s\_{i,j} x\_{i,j,d}$, where $s\_{i,j}$ is the score for the matchup between teams $i$ and $j$. Then, you can feed this to an off-the-shelf ILP solver, such as Gurobi or CPLEX, and it will (hopefully) find for you the optimal schedule.

---
Tags: algorithms, scheduling, heuristics
---


# Question
Title: Context Free Grammar to Regular Expression?
I want to learn whether I can create regular expressions from the given Context Free Grammar. I found some examples that can be translated to regular expressions. However, all of them were like this: "S-\> aB | bC". Whereas my example is like: "S-\> AB | BC". Here is my example:

Can I create RE's from this? What is the reason? I want to fully understand why I can and why I cannot. Thank you.

# Answer
The set of all regular languages is a subset of context free languages. So if you have a context free grammar (CFG) that generates a regular languages, you most certainly can convert it to a regular expression (RE), regular grammar (RG), or finite automata (FA).

Before I go further with your example, I will simplify it so that we only deal with 3 terminals (instead of 8). In the example below, the terminals `a,b,c` will be represented by the single terminal `a`, the terminals `x,y,z` will be represented by `x`, and the terminals `p,q` will be represented by `p`.

```
S -> N V
N -> a N | N N | N a | x
V -> N V | p

```

There is no real procedure in converting it, so we will take it step by step. First we need to see what kinds of strings the variable `N` can produce.

We can see that for every `N` introduced, it terminates with `x`. The `a`'s can be on either side of `x` and repeat as many times as needed. This entire pattern can be repeated as many times as needed, but be produced at least once. So `N` generates the same strings as $(a^\*x^+a^\*)^+$ RE.

Next we look at `V`. It can produce any amount of `N`'s but must terminate with a single `p`. So we have $((a^\*x^+a^\*)^+)^\*p = (a^\*x^+a^\*)^\*p$.

Finally, `S` produces `NV` which is similar to our RE for `V`. Note that there is at least one `N` produced. So that CFG is converted to $(a^\*x^+a^\*)^+p$.

To put it in terms of your original grammar, it would look something like this $((a|b|c)^\*(x|y|z)^+(a|b|c)^\*)^+(p|q)$. Again, because of the amount of terminals in the original grammar, it is easier to simply things to help see the pattern the grammar is actually showing.

As a disclaimer, this is not a proof, but it shows the reasoning as to how I created an RE from the CFG you provided. To know if this is correct, you would need to know the exact language the CFG produces. Unfortunately, the grammar is not easily recognizable.

I used the following CFG Developer tool to help see a pattern from your grammar.
> 6 votes

# Answer
To deal with the issue cogently requires first some background. These issues can be dealt with, entirely, within an algebraic framework. Algebraically, a grammar is a system of fixed-point inequations over a certain type of partially ordered algebra, with the item represented by the grammar given in terms of the least fixed point solution of the system.

The algebra underlying regular expressions is known as the Kleene Algebra. A weaker first-order formulation of the algebra is as a partially ordered monoid which possesses least upper bounds for finite subsets (particularly, with the least upper bounds $⋁ ∅ = 0$ and $⋁ \\{a,b\\} = a + b$, the latter also written as $a | b$), with the least upper bound distributive over the product; such that all linear systems possess least fixed point solutions. Axioms may be presented as follows

Monoid: $x(yz) = (xy)z, x1 = x = 1x$

Least Upper Bound: $x + (y + z) = (x + y) + z, x + 0 = x = 0 + x, x + y = y + x, x + x = x$

Distributivity: $x0y = 0, w(x + y)z = wxz + wyz$

with the partial ordering defined by $x ≥ y ⇔ ∃z: x = z + y ⇔ x = x + y$. (This reverses the order in which $+$ and $≥$, are given, by making $+$ the more fundamental of the two.)

The least solution of the fixed point inequality $x ≥ 1 + ax$ is $x = a^\*$, which defines the star operator. The last axiom may be given in any one of a large number of forms; such as the requirement that the least fixed point solution to $x ≥ a + bx + xc$ be $x = b^\* a c^\*$. I think you also need $0^\* = 1$ paired off with this axiom in order to recover $1 + a a^\* = a^\* = 1 + a^\* a$. There are several other axiom sets that do the same job as these two.

A stronger axiomatization (which, technically, is not first order since it is infinitary) replaces the least fixed point solvability requirement by the following:

\*-continuity: $⋁\_{n≥0} \left(a b^n c\right) = a b^\* c$

and defines $a^\*$ as $⋁\_{n≥0} a^n$.

The free Kleene algebra over a set $X$ is one and the same as the algebra of regular expressions taken over $X$ as the alphabet. The free extension of a monoid $M$ to a \*-continuous Kleene algebra is one and the same as the family $ℜM$ of "rational subsets" of $M$. The Kleene operations, for it, are defined as $$0 = ∅, A + B = A ∪ B, AB = \\{ ab ∈ M: a ∈ A, b ∈ B \\},$$ for subsets $A, B ⊆ M$, where the individual elements of $M$ itself are included within the algebra by identifying each $m ∈ M$ with its corresponding singleton set $\\{m\\}$. The partial ordering is the subset order $A ≤ B ⇔ A ⊆ B$, for $A, B ⊆ M$, and the Kleene star (by the \*-continuity property) is given as $$A^\* = ⋃\_{n≥0} A^n$$ (where $A^0 = \\{1\\}, A^1 = A, A^2 = A A$, etc.), for subsets $A ⊆ M$.

The rational subsets $ℜM$ of a monoid $M$ comprise the family of subsets obtained from the finite subsets of $M$ by the Kleene operations. For a finite alphabet $X$, and its corresponding free monoid $X^\*$, the Kleene algebra $ℜX^\*$ is the algebra of regular expressions over $X$. But also: for two alphabets $X$ and $Y$ (which we may think of respectively as inputs and outputs), $ℜ\left(X^\*×Y^\*\right)$ is the Kleene algebra of "rational transductions" between alphabets $X$ and $Y$. This can be generalized to $n = 3, 4, 5, ...$ alphabets, defining rational transductions that have 3 or more channels or tiers.

A stronger axiom, still, asserts the existence of not just linear least fixed point solutions, but also least fixed point solutions to non-linear inequalities, $x ≥ f(x)$, where $f(x)$ is a Kleene-algebraic function formed from $x$, with the corresponding least fixed point being defined as $μx f(x)$. In place of the \*-continuity axiom, one may pose

μ-continuity: $⋁\_{n≥0} \left(a f^n(0) c\right) = a \left(μx f(x)\right) c,$

where $f^0(x) = x$, $f^1(x) = f(x)$, $f^2(x) = f(f(x))$, etc.

These are the μ-continuous Chomsky Algebras (or I'll just call them Chomsky algebras for short). (*Edit*: the left context $a$ and right context $c$, omitted by accident, were added back in. The μ-continity property is supposed to be a generalization of \*-continuity.)

They define the algebra of context-freeness. The free algebra generated by a set $X$ is the family $ℭX^\*$ of context-free subsets of $X^\*$; i.e. context-free languages over the alphabet $X$. Similarly, $ℭ\left(X^\*×Y^\*\right)$ comprise the push-down transductions from alphabet $X$ to $Y$ and, generally, the family $ℭM$ of context-free subsets of a monoid $M$ comprise the Chomsky-algebra freely generated from $M$. A yacc grammar, for instance, is actually a push-down transduction since it has both input symbols and, effectively, output symbols (each item in a yacc grammar enclosed in { ... } may be regarded as a single output symbol).

So, with that background out of the way, we get to your problem. Your grammar, written as a system of inequalities over a Kleene algebra is $$S ≥ N V$$ $$N ≥ A N + N N + N A$$ $$A ≥ a + b + c$$ $$N ≥ x + y + z$$ $$V ≥ N V$$ $$V ≥ p + q$$ or equivalently $$S ≥ N V$$ $$N ≥ A N + N N + N A + Z$$ $$A ≥ a + b + c$$ $$V ≥ N V + Q$$ where, for convenience, we define $Z = x + y + z$ and $Q = p + q$.

In any Kleene algebra, the least fixed point solution to $x ≥ a + bx + xc + xdx$ is $x = b^\* a c^\* \left(d b^\* a c^\*\right)^\*$ \- that's a theorem of Kleene algebras. This can be applied to eliminate and reduce a system containing an inequality of this form. Thus we have (with $(Z,A,A,1)$ in place of $(a,b,c,d)$ and $N$ in place of $x$):

$$N ≥ A^\* Z A^\* \left(1 A^\* Z A^\*\right)^\* = A^\* Z A^\* \left(A^\* Z A^\*\right)^\*.$$

Using basic properties of Kleene algebras, such as $x(yx)^\* = (xy)^\*x$, $x^\* x^\* = x^\*$, we can write

$$N ≥ A^\* Z A^\* \left(Z A^\*\right)^\*.$$

For $V$, we have a reduction to

$$V ≥ N^\* Q.$$

Now, back-substitute into $S$

$$S ≥ N N^\* Q ≥ A^\* B B^\* \left(A^\* B B^\*\right)^\* Q,$$

where $B = Z A^\*$. Apply basic Kleene identities, such as $1 + y^\* = y^\*$, $c^\* \left(d c^\*\right)^\* = (c + d)^\*$ and $x + y^\*x = \left(1 + y^\*\right) x = y^\* x$ to get

$$A^\* B B^\* \left(A^\* B B^\*\right)^\* = A^\* B \left(B + A^\* B\right)^\* = A^\* B \left(A^\* B\right)^\* = A^\* \left(B A^\*\right)^\* B.$$

Substituting back in $B = Z A^\*$, we get

$$S ≥ A^\* \left(Z A^\* A^\*\right)^\* Z A^\* Q = A^\* Z \left(A^\* Z\right)^\* A^\* Q = A^\* Z \left(A + Z\right)^\* Q.$$

To get the final result for $S$, substitute in $A = a + b + c$, $Q = p + q$ and $Z = x + y + z$.

So, each $S$ consists of a bunch of $A$ and $Z$ elements, containing at least one $Z$ element, suffixed by a $Q$ element.

For a system such as $S ≥ u S v + w$, no least fixed point solution exists, in general for Kleene algebras, so the solution does not exist as any regular expression in $ℜ\\{u,v,w\\}^\*$. Instead, you need to extend the Kleene algebra by adding elements $, , , $ satisfying the properties

$$ = 1 = , = 0 = .$$

This algebra is known as $C\_2'$ and is a polycyclic Kleene algebra. The strong version of it, known as $C\_2$ also contains the axiom

$$ + = 1.$$

It has the additional property that it contains *every single one* of its finite-dimensional vector and matrix algebras, but it is more than what we need here.

We also postulate that elements of $C\_2'$ commute with the expressions we use the additional elements with - here: the set $X = \\{ u, v, w \\}$. The resulting algebra is a tensor product $C\_2' ⊗ ℜX^\*$ of $C\_2'$ and $ℜX^\*$.

For an arbitrary monoid $M$, the *algebraic form* of the Chomsky-Schütenberger Theorem asserts that every context-free subset of $M$, i.e. all the members of $ℭM$, exist as elements of $C\_2' ⊗ ℜM$ and that, in fact, it comprises *all* the members of this tensor product that commute with $C\_2'$. That is: every non-linear fixed point system over $ℜM$ has a least fixed point solution in $C\_2' ⊗ ℜM$ and that this, in fact, contains the fixed point closure of $ℜM$, i.e., $ℭM$, itself.

All of this takes place within the framework of \*-continuous Kleene algebras. The weak first-order axiomatization for Kleene algebras is not strong enough to get the job done ...

*Digression Begins*

... unless the Kleene algebras are commutative. All commutative Kleene algebras are fixed-point closed and, in fact, for a univariate system $μx f(x) = f'(f(0))^\* f(0)$, for any non-linear Kleene algebraic function $f(x)$. Derivatives are defined by $d(x^\*)/dx = x^\*$, and for commutative Kleene algebras, the Kleene-star satisfies the laws of exponents $(x+y)^\* = x^\* y^\*$ and $0^\* = 1$. It is conjectured that the multivariate systems have least fixed point solutions $μx f(x) = f'\left(f'(f(0))^\* f(0)\right)^\* f(0)$, and bear in mind that's a vector-matrix equation, since $f'(x)$ is a Jacobian matrix, for multivariate functions $f(x)$.

That's the algebraic form of the Parikh Theorem, which may be regarded as the commutative version of the algebraic version of the Chomsky-Schützenberger Theorem. It works with the weaker first-order Kleene algebra axioms and does not need \*-continuity.

*Digression Ends*

For the non-commutative case, when the algebraic Chomsky-Schützenberger Theorem is applied here, the least fixed point solution to $S ≥ u S v + w$ is $μs.(usv + w)$ which is equivalently given by the Chomsky-Schütenberger context-free expression $S = μs.(usv + w) = (u)^\* w (v)^\* $.

If you took out the bracketing $,$, you'd get the following expression $(u)^\* w (v)^\*$, which reduces to the following *normal form* $$(u)^\* w (v)^\* = (u)^\* u S + S + S v (v)^\*.$$ Since $S$ commutes with $$ and $$, we could also write $$(u)^\* w (v)^\* = (u)^\* u S + S + S v (v)^\* = ((u)^\* u + 1) S = (u)^\* S,$$ using the Kleene algebraic identity $x^\*x + 1 = x^\*$. The last term cancelled since $ = 0$. Similarly, $$(u)^\* w (v)^\* = (u)^\* u S + S + S v (v)^\* = S(1 + v (v)^\*) = S(v)^\*.$$

Compare the non-commutative solution with the commutative case, by the way, for $μs.f(s)$ with $f(s) = usv + w$, $f'(s) = uv$ and $f(0) = w$, where we get $μs.f(s) = f'(f(0))^\* f(0) = (uv)^\* w$.

This is all recent (except the algebraic Parikh Theorem, which is 1999), though its precursors exist on the USENET, back to the early 1990's, Chomsky, himself, was brought up to date on the new developments a few years ago, though he expresses regret that he wasn't able to keep active with this work. The Chomsky-Schützenberger Theorem is almost 60 years old, with its algebraic versions going back over 30 years now.

*The evolution of recent developments in formal language theory from the 1960's*

https://www.scribd.com/document/392094748/The-evolution-of-recent-developments-in-formal-language-theory-from-the-1960-s

In the near future, these and other related materials will be linked to from within The Federation Archive on GitHub.
> 3 votes

---
Tags: context-free, regular-expressions
---


# Question
Title: Struggling to find loop invariant in power function
I am struggling to find a good loop invariant for the following function, which returns a^b where a is a real number and b is a natural number:

```
power <- function(a, b){
     c <- 1
     while(b > 0){
          if(b %% 2 == 1){
               c <- c * a
          }
          b <- floor(b / 2)
          a <- a * a
     }
     return c
}

```

I've ran through the loop with a couple of examples, and I see that it has 2 kinds of cases; when b is even or odd. I also understand that on the kth iteration, a = a\_0^(2^k), but I am struggling to find a proper invariant as there is no real iterating variable to use.

# Answer
It may clarify things to use different variable names. Let's call $x$ the desired result of $a^b$ where $a$ and $b$ are the inputs. With variables $c', a', b'$ initialized to $c' = 1, a'=a, b'=b$, you are basically maintaining that $x = c'(a')^{b'}$. At the end you have $x = c'$ because $b' = 0$. Each step "transfers" half of the exponent to the base of the exponentiation, or in the odd case, the coefficient.
> 0 votes

---
Tags: correctness-proof, loop-invariants
---


# Question
Title: How can I find a Stable Diffusion program?
Well, I know that I'm going to ask too much.

So, I really want to ask you a totally (powerful (!)) free completely off-line code to generate **prompt-based** images like midjourney. I want to run with my graphics card and memory without any restrictions of time or number of images and completely private.

**My question is: do you know where to find these codes?**

*(!) that is in the same level of midjourney, night café and NOP's Colab stable*

# Answer
> 1 votes
These instructions aren't too bad: https://www.howtogeek.com/830179/how-to-run-stable-diffusion-on-your-pc-to-generate-ai-images/

...but you'll do better by googling for install instructions specific to your OS. Stable Diffusion has different installer packages for Windows, OSX, and Linux, and getting instructions specific to the platform you're using will make things a bit easier.

---
Tags: machine-learning, reference-request, artificial-intelligence, computation-models, image-processing
---


title: Recurrence Relation Proof check

text:
# Question
Title: Recurrence Relation Proof check
A question I was given

$T(0) = 1,$ $T(1)=0,$ $T(n)= 2T(n-2)$

I think the possible solution is $T(n)=2^n$

Proof: by induction. Base Case:

$n=0$ $T(0)=2^0=1$

Inductive Hypothesis: Assume for some $n$. $T(n)=2^n$ Show for $n+1$

$T(n+1)= 2(T(n-1))$ $=2(2^{n-1})$ $=2^n$

which is what I proposed. Is this correct? I'm a little confused because it says that $T(1)=0$, so it wouldn't make sense for $t(n)=2^n$. But I don't know how else I could prove the recurrence relation given as stated above.

# Answer
> 1 votes
This can be verified using the Master Theorem for decreasing functions

The recurrence relation can be written as $T(n)=2T(n-2)+O(1)$.

Comparing with the general recurrence here $a=2$, $b=2, k=0$

Using Case 2 of the theorem we get $T(n)= O(2^{\frac{n}{2}}\*n^0) = O(2^{\frac{n}{2}})$

Even if you don't know the theorem, for such standard recurrences, one way is to draw the recurrence tree for it, and you can quickly figure out the same.

---
Tags: recurrence-relation, check-my-answer
---


# Question
Title: Minimizing/Maximizing recursion depth for DFS
The idea for this problem comes from GATE CS 2014 Set-3 Q13.

Given a graph, are there any heuristics to figure out a DFS traversal which has minimum/maximum recursion depth?

Consider the graph from the question, labelled

Consider the DFS traversal **a-b-c-f-e-d-g-h-i-j-k-l-m-n-q-p-o-r-s-t-u** with a recursion depth of 19. The numbers represent the recursion depth as per the question

Now consider the traversal **j-k-l-m-p-s-r-o-t-q-u-n-i-f-e-d-a-b-c-g-h**, which has a recursion depth of 8.

While it is easy to figure this out for a small enough graph and on paper, I am struggling to find a well defined algorithm/heuristic to do so. My intuition in minimizing was to find an articulation point in the graph which would split it into the maximum number of subgraphs(hence **j** as a starting vertex), and for maximizing, a node with minimum degree which is not adjacent to an articulation point(hence discarding **k** and **u** and selecting **a** as starting vertex but any other similar vertex would do).

Is there a name for this problem, and any approaches to solve(other than brute force)?

# Answer
Unfortunately, I think that that there is a reduction from the longest path problem, which have a $\mathsf{NP}$-complete decision version (finding the maximum depth is equivalent to finding the longest path between two vertices).

A possible approximation heuristic would be running a DFS from an arbitrary vertex, then running it again from the leaf farthest from the root in the traversal tree.

This post gives a dynamic programming exact algorithm for finding longest paths.
> 2 votes

---
Tags: graphs, data-structures, recursion, graph-traversal, depth-first-search
---


title: Hoare's Partition Scheme Stuck

text:
# Question
Title: Hoare's Partition Scheme Stuck
I'm tracing through a quick sort algorithm on paper, but I keep getting stuck on the partitioning using Hoare's partitioning. The array is `{3,1,4,1,5,9,2,6,5,3,5}`. I'm using median of three for the pivot, so pivot is 5, I swap the pivot with the left and have `{5,1,4,1,5,9,2,6,5,3,3}`. I go through the algorithm as follows

1. Swap A\[4\] with A\[10\]: A= `{5,1,4,1,3,9,2,6,5,3,5}`
2. Swap A\[5\] with A\[10\]: A= `{5,1,4,1,3,5,2,6,5,3,9}`
3. Swap A\[5\] with A\[9\]: A= `{5,1,4,1,3,3,2,6,5,5,9}`
4. Swap A\[7\] with A\[9\]: A= `{5,1,4,1,3,3,2,5,5,6,9}`

So I have the pointers stuck on the the two 5's at A\[7\] and A\[8\], but Hoare's keeps telling me to flip those two because i \< j so I have to keep flipping. I know there's something I'm doing wrong, but I don't understand what it is.

# Answer
> 2 votes
Since your pivot value is 5, the comparison with A\[7\] and A\[8\], which are both 5, will be `=pval`.

While you didn't share the pseudocode you used, I believe you used a while loop for incrementing/decrementing the pointers. This means the pointers will just be stuck at A\[7\] and A\[8\] as they do not satisfy the expressions `<pval` or `>pval`.

Instead of using a while loop, you should pre-decrement the left pointer and pre-increment the right pointer, then use a do-while loop. This will ensure that the pointers will increment/decrement at least once even if it is `=pval`.

This website has an implementation of both Hoare's and Lomuto schemes. https://www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/

---
Tags: sorting, quicksort
---


# Question
Title: Why is the complexity of BFS O(V+E) instead of O(V*E)?
CLRS pseudocode:

```
begin
   for each vertex u in G.V - {s}, do
      u.color := white
      u.d := infinity
      u.p := NIL
   done
   s.color := green
   s.d := 0
   s.p := NIL
   Q := NULL
   insert s into Q
   while Q is not null, do
      u = delete from Q
      for each v in adjacent to u, do
         if v.color = white
            v.color := green
            v.d := u.d + 1
            v.p := u
            insert v into Q
         end if
      done
      u.color = dark_green
   done
end`

```

In the clrs it says that the insertion and deletion operations with the queue require an O (1) time, so the total time of operations with the queue is O (V). (V because each vertex is visited at least once). instead the time to inspect the adjacency list of each node is O (E). Then we have another O (V) for initialization. So the total time is O (V + E) which in the worst case becomes O (V ^ 2), this depends on whether the graph is dense or not.

Now my question is: Since we have two cycles nested the complexity shouldn't be O (V * E), I can't understand why a sum operation is performed instead of multiplying.

# Answer
> 1 votes
I will suppose here that the graph is undirected, but the same reasonning can be done with a digraph.

Using an implemention of a graph as an array of adjacency lists, the adjacency list of any vertex $v$ is its number of neighbors, $\deg(v)$.

The BFS inspects each adjacency list at most once during the graph traversal (and exactly once if the graph is connected). That means that the total complexity is: $$\mathcal{O}\left(\sum\limits\_{v\in V}(\deg(v) + 1)\right)$$ Here, the $+1$ is necessary, as inspecting an adjacency list costs $\mathcal{O}(1)$ time, even if the list is empty. Now, a very useful formula for complexity on graphs is: $$\sum\limits\_{v\in V}\deg(v) = 2|E|$$ It can be proven quite easily when noting that each edge increases the sum of degrees by two (one for each extremity).

Finaly, we conclude that the complexity is: $$\mathcal{O}\left(\sum\limits\_{v\in V}(\deg(v) + 1)\right) = \mathcal{O}(2|E| + |V|) = \mathcal{O}(|E| + |V|)$$

---
Tags: complexity-theory, graphs, time-complexity, graph-traversal, big-o-notation
---


# Question
Title: What do queues and stacks correspond to in math?
Many (and I suspect all) abstract data types in CS correspond to some math concepts, and even share the same names, for example, set, map, record/tuple, ....

As abstract data types, what do queues and stacks correspond to in math? For example, some special paths in graph theory?

Have stacks and queues been treated mathematically and, if so, how are they usually treated within mathematic?

What mathematical concepts form the basis for stacks and queues?

Are there references that introduce data structures as models of monoids and other algebraic concepts? (Raphael said data structures are)

# Answer
As a practical matter, how you treat data structures mathematically largely depends what you're trying to do.

For example, suppose that you're trying to reason about the correctness of programs that use stacks and/or queues. In that situation, you'd want to treat the stack/queue as an abstract object, and axiomatise its properties. So you develop (say) a theory of stacks which can be layered on top of a general theorem prover.

You can do this quite straightforwardly in constructive type theories, such as the calculus of constructions. It's worth taking a look at the theories that come with Coq (the proof management system); it has a theory of strings, a theory of lists, a theory of maps, and so on.

Having said that, stacks and queues in some contexts do model mathematical objects. I'm going to run with the example of pushdown automata. In this case, the stack symbols are a fixed finite set (and they have no structure; it makes no sense to do maths on the stack symbol names themselves!), and so the stacks form an interesting algebra.

I'm going to start with regular languages, which we can axiomatise as a Kleene algebra. A Kleene algebra is an idempotent semiring plus the Kleene star operator. The two ring-like operations $\cdot$ and $+$ correspond to concatenation and set union, and $0$ and $1$ correspond to the null set and the empty string.

We know that DFAs and regular expressions describe the same class of languages. We also know that pushdown automata are like DFAs, only they also do stack operations. So there's no reason why we can't put stack operations in regular expressions; in this way, we could express context-free languages using a regular expression-like operation.

So let's do that. We'll denote a stack push of symbol $i$ using the notation $\left\langle i \right|$ and a pop using the notation $\left| i \right\rangle$. Now we need to work out how these stack operations work algebraically.

Terminal symbols commute with stack operations, in the sense that reading as symbol followed by a stack push or pop is the same as doing the stack operation followed by reading the symbol:

$$a \left\langle i \right| = \left\langle i \right| a$$ $$a \left| i \right\rangle = \left| i \right\rangle a $$

Finally, we need to work out what happens when two stack operations meet. A push of a symbol followed by a pop of the same symbol is equivalent to reading the empty string (i.e. doing nothing):

$$\left\langle i \right| \left| i \right\rangle = 1$$

However, pushing a symbol followed by trying to pop a different symbol cannot happen. This is equivalent to the empty set (i.e. the language with no strings in it):

$$\left\langle i \right| \left| j \right\rangle = 0, \hbox{if}\\,i \ne j$$

In other words, we're looking at something very like a vector space. Strings of terminals behave like scalars, and stack operations behave like vectors and one-forms. When a push meets a pop, they behave like an inner product where the basis vectors are orthonormal.

Moreover, if the stack is nonempty, then any pop followed by a push of the same symbol should be a no-op:

$$\left| 1 \right\rangle \left\langle 1 \right| + \left| 2 \right\rangle \left\langle 2 \right| + \cdots + \left| n \right\rangle \left\langle n \right| = 1$$

Using this algebra, we can (say) express $a^n b^n$ as $\left\langle 1 \right| (a \left\langle 2 \right|)^\* (b \left| 2 \right\rangle)^\* \left| 1 \right\rangle$. It's a little unwieldy, but it works.

Attentive readers might have caught on why I used this notation (lovingly stolen from Mark Hopkins): this is a an inner product space using Paul Dirac's bra-ket notation, as used in quantum mechanics.

(As an aside, it turns out that the analogy goes quite deep. A Turing machine can be thought of as an automaton with two stacks, and if you allow gradations between $0$ and $1$, you can axiomatise quantum Turing machines.)

However, this is not the point I'm trying to get across. The point is that in this case, *this* use of stack operations (over a finite set of symbols) form an interesting algebra which was discovered in a completely different context. *Other* uses may not.

This alone answers your question with a resounding "it depends".
> 9 votes

# Answer
Honestly, the best and maybe simplest way to think about how to model data structures in proper mathematical form is to simply attempt to implement them in a functional language for which the resulting map from some space to another space may result in something familiar; whether it be groupoid, group, ring, monoid, vector space, algebra, graph, etc., or something unrecognizable, or some amalgamation of a few things that look or behave familiar. Once you have an idea what the structure is you can investigate actions on the object (like group actions or products or quotients, push forwards and pull backs, etc) and those may correspond to the regular operations you would like to see from the data structure.

So, go model it in Haskel or F#, let’s say, and let the transformations speak for themselves.
> 0 votes

---
Tags: terminology, data-structures, discrete-mathematics
---