# Question
Title: Why is writing down mathematical proofs more fault-proof than writing computer code?
I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs.

It seems that this is something more widespread than just my experience. Most people make software bugs all the time in their programming, and they have the compiler to tell them what the mistake is all the time. I've never heard of someone who wrote a big computer program with no mistakes in it in one go, and had full confidence that it would be bugless. (In fact, hardly any programs are bugless, even many highly debugged ones).

Yet people can write entire papers or books of mathematical proofs without any compiler ever giving them feedback that they made a mistake, and sometimes without even getting feedback from others.

Let me be clear. this is not to say that people don't make mistakes in mathematical proofs, but for even mildly experienced mathematicians, the mistakes are usually not that problematic, and can be solved without the help of some "external oracle" like a compiler pointing to your mistake.

In fact, if this wasn't the case, then mathematics would scarcely be possible it seems to me.

**So this led me to ask the question: What is so different about writing faultless mathematical proofs and writing faultless computer code that makes it so that the former is so much more tractable than the latter?**

One could say that it is simply the fact that people have the "external oracle" of a compiler pointing them to their mistakes that makes programmers lazy, preventing them from doing what's necessary to write code rigorously. This view would mean that if they didn't have a compiler, they would be able to be as faultless as mathematicians.

You might find this persuasive, but based on my experience programming and writing down mathematical proofs, it seems intuitively to me that this is really not explanation. There seems to be something more fundamentally different about the two endeavours.

My initial thought is, that what might be the difference, is that for a mathematician, a correct proof only requires every single logical step to be correct. If every step is correct, the entire proof is correct. On the other hand, for a program to be bugless, not only every line of code has to be correct, but its relation to every other line of code in the program has to work as well.

In other words, if step $X$ in a proof is correct, then making a mistake in step $Y$ will not mess up step $X$ ever. But if a line of code $X$ is correctly written down, then making a mistake in line $Y$ will influence the working of line $X$, so that whenever we write line $X$ we have to take into account its relation to all other lines. We can use encapsulation and all those things to kind of limit this, but it cannot be removed completely.

This means that the procedure for checking for errors in a mathematical proof is essentially linear in the number of proof-steps, but the procedure for checking for errors in computer code is essentially exponential in the number of lines of code.

What do you think?

**Note: This question has a large number of answers that explore a large variety of facts and viewpoints. Before you answer, please read *all of them* and answer only if you have something new to add.** Redundant answers, or answers that don't back up opinions with facts, may be deleted.

# Answer
Let me offer one reason and one misconception as an answer to your question.

The **main reason** that it is easier to write (seemingly) correct mathematical proofs is that they are written at a very high level. Suppose that you could write a program like this:

```
function MaximumWindow(A, n, w):
    using a sliding window, calculate (in O(n)) the sums of all length-w windows
    return the maximum sum (be smart and use only O(1) memory)

```

It would be much harder to go wrong when programming this way, since the *specification* of the program is much more succinct than its *implementation*. Indeed, every programmer who tries to convert pseudocode to code, especially to efficient code, encounters this large chasm between the *idea* of an algorithm and its *implementation details*. Mathematical proofs concentrate more on the ideas and less on the detail.

The real counterpart of code for mathematical proofs is *computer-aided proofs*. These are much harder to develop than the usual textual proofs, and one often discovers various hidden corners which are "obvious" to the reader (who usually doesn't even notice them), but not so obvious to the computer. Also, since the computer can only fill in relatively small gaps at present, the proofs must be elaborated to such a level that a human reading them will miss the forest for the trees.

An important **misconception** is that mathematical proofs are often correct. In fact, this is probably rather optimistic. It is very hard to write complicated proofs without mistakes, and papers often contain errors. Perhaps the most celebrated recent cases are Wiles' first attempt at (a special case of) the modularity theorem (which implies Fermat's last theorem), and various gaps in the classification of finite simple groups, including some 1000+ pages on quasithin groups which were written 20 years after the classification was supposedly finished.

A mistake in a paper of Voevodsky made him doubt written proofs so much that he started developing homotopy type theory, a logical framework useful for developing homotopy theory formally, and henceforth used a computer to verify *all* his subsequent work (at least according to his own admission). While this is an extreme (and at present, impractical) position, it is still the case that when using a result, one ought to go over the proof and check whether it is correct. In my area there are a few papers which are known to be wrong but have never been retracted, whose status is relayed from mouth to ear among experts.
> 251 votes

# Answer
*(I am probably risking a few downvotes here, as I have no time/interest to make this a proper answer, but I find the text quoted (and the rest of the article cited) below to be quite insightful, also considering they are written by a well-known mathematician. Perhaps I can improve the answer later.)*

The idea, which I suppose isn't particularly distinct from the existing answer, is that a "proof" or argument communicates to a mathematical community, where the purpose is to convince them that the (tedious) details can be filled, in principle, to attain a fully specified formal proof -- without often doing so at all. One critical instance of this is that you can use existing theorems by simply stating them, but code re-use is much more challenging in general. Also consider minor "bugs", which may completely render a piece of code useless (e.g., it SEGFAULTs) but may leave a mathematical argument largely intact (that is, if the error can be contained without the argument collapsing).

> The standard of correctness and completeness necessary to get a computer program to work at all is a couple of orders of magnitude higher than the mathematical community's standard of valid proofs. Nonetheless, large computer programs, even when they have been very carefully written and very carefully tested, always seem to have bugs. \[...\] Mathematics as we practice it is much more formally complete and precise than other sciences, but it is much less formally complete and precise for its content than computer programs. The difference has to do not just with the amount of effort: the kind of effort is qualitatively different. In large computer programs, a tremendous proportion of effort must be spent on myriad compatibility issues: making sure that all definitions are consistent, developing "good" data structures that have useful but not cumbersome generality, deciding on the "right" generality for functions, etc. The proportion of energy spent on the working part of a large program, as distinguished from the bookkeeping part, is surprisingly small. Because of compatibility issues that almost inevitably escalate out of hand because the "right" definitions change as generality and functionality are added, computer programs usually need to be rewritten frequently, often from scratch.

ON PROOF AND PROGRESS IN MATHEMATICS (pp. 9-10), by WILLIAM P. THURSTON https://arxiv.org/pdf/math/9404236.pdf
> 88 votes

# Answer
Allow me to start by quoting E. W. Dijkstra:

> "Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians." (from EWD498)

Although what Dijkstra meant with \`programming' differs quite a bit from the current usage, there is still some merit in this quote. The other answers have already mentioned that the level of abstraction in mathematics is allowed to be a lot higher than in programming, meaning we can ignore some tricky parts if we wish to do so.

However, I believe that this is merely a consequence of a more fundamental difference between a proof and a computer program, which is their *purpose*.

The main purpose of a mathematical proof is, among others, to convince oneself that a mathematical claim is correct and, perhaps even more important, achieving *understanding*. Therefore, you may choose to only work in the mathematical world, where everything is created such that understanding can be reached *by design* (although some students beg to differ...) This is precisely what Dijkstra meant with "pure mathematicians", those who (almost) only concern themselves with mathematical facts and understanding their properties.

So, you should not be surprised producing correct proofs is relatively fault-proof: it is the point of the entire "exercise". (Still, this doesn't mean mistakes don't or barely exist, to err is only human, they say)

Now, if we consider programming, what is our purpose? We do not really seek understanding, we want something that *works*. But when does something "work"? Something works when we have successfully created something that allows some strange machine to complete the task we want it to do and preferably pretty fast too.

This is, I believe, the fundamental difference, as it means that our goal cannot simply be stated as some theorem which our program "proves", we desire something in the *real world* (whatever that is), not some mathematical artifact. This means that we cannot purely theoretically achieve our goal (although Dijkstra would have you try it irregardless) as we must appease the machine, hope that we actually know which task we want it to do and also be aware of things none considered, yet happen somehow.

So, in the end, there is no other way around than to just try it and probably fail, fix, fail and try again until we are somewhat satisfied with the result.

---

Note that your hypothesis writing fault-less proofs is simpler than fault-less programs (which are in fact different statements as @Ariel points out) may be in fact wrong, as proofs are often constructed via trial and error at some level. Still, I hope that this sheds some light on the question that is implied: "What really is the difference between proving some theorem and writing a program?" (To which a careless observer of the Curry-Howard correspondence might say: "Nothing at all!")

---

As @wvxvw mentioned in the comments, the following paragraphs from 'notes on Structured Programming' (EWD249, page 21) is very relevant:

> (...) A program is never a goal in itself; the purpose of a program is to evoke computations and the purpose of the computations is to establish a desired effect. Although the program is the final product made by the programmer, the possible computations evoked by it - the "making" of which is left to the machine! - are the true subject matter of his trade. For instance, whenever a programmer states that his program is correct, he really makes an assertion about the computations it may evoke.
>
> (...) In a sense the making of a program is therefore more difficult than the making of a mathematical theory: both program and theory are structured, timeless objects. But while the mathematical theory makes sense as it stands, the program only makes sense via its execution.
> 64 votes

# Answer
Lamport provides some ground for disagreement on prevalence of errors in proofs in How to write a proof (pages 8-9):

> Some twenty years ago, I decided to write a proof of the Schroeder-Bernstein theorem for an introductory mathematics class. The simplest proof I could find was in Kelley’s classic general topology text. Since Kelley was writing for a more sophisticated audience, I had to add a great deal of explanation to his half-page proof. I had written five pages when I realized that Kelley’s proof was wrong. Recently, I wanted to illustrate a lecture on my proof style with a convincing incorrect proof, so I turned to Kelley. I could find nothing wrong with his proof; it seemed obviously correct! Reading and rereading the proof convinced me that either my memory had failed, or else I was very stupid twenty years ago. Still, Kelley’s proof was short and would serve as a nice example, so I started rewriting it as a structured proof. Within minutes, I rediscovered the error.
>
> ... The style was first applied to proofs of ordinary theorems in a paper I wrote with Martin Abadi. He had already written conventional proofs—proofs that were good enough to convince us and, presumably, the referees. Rewriting the proofs in a structured style, we discovered that almost every one had serious mistakes, though the theorems were correct. Any hope that incorrect proofs might not lead to incorrect theorems was destroyed in our next collaboration. Time and again, we would make a conjecture and write a proof sketch on the blackboard—a sketch that could easily have been turned into a convincing conventional proof—only to discover, by trying to write a structured proof, that the conjecture was false. Since then, I have never believed a result without a careful, structured proof. My skepticism has helped avoid numerous errors.
> 53 votes

# Answer
One big difference is that programs typically are written to operate on inputs, whereas mathematical proofs generally start from a set of axioms and prior-known theorems. Sometimes you have to cover multiple corner cases to get a sufficiently general proof, but the cases and their resolution is explicitly enumerated and the scope of the result is implicitly constrained to the cases covered.

Compare this with a computer program, which has to provide 'correct' output for a range of possible inputs. It's rarely possible to enumerate all inputs and try them all. Worse yet, suppose the program interacts with a human being and allows their input to modify the functioning? Human beings are notoriously unpredictable and the number of possible inputs to a reasonably large program with human interaction grows at a prodigious rate. You need to try to foresee all the different ways a program might be used and try to make all those use cases either work or at least fail in a reasonable way, when failure is the only option. And that's assuming you even know how it's *supposed* to work in all those obscure corner cases.

Finally, a large program can't really be compared to a single proof, even a complex one. A large program is probably more akin to collecting and reviewing a small library of literature, some of which may have errors which you need to work around. For programs more on the scale of a single proof, which might be a small algorithm implementation, let's say, experienced software engineers can/do complete them without making mistakes, especially when using modern tools that prevent/resolve common trivial errors (like spelling mistakes) which are equivalent to early issues you'd resolve in proofreading.
> 43 votes

# Answer
*They say the problem with computers is that they do **exactly** what you tell them.*

I think this might be one of the many reasons.

Notice that, with a computer program, the writer (you) is smart but the reader (CPU) is dumb.
But with a mathematical proof, the writer (you) is smart and the reader (reviewer) is also smart.

This means you can never afford to get into a "well, you know what I *mean*" situation with a computer. It does exactly what you tell it, without knowing your intentions.

For example, let's say this is a step in some proof:

\begin{align\*} \displaystyle\frac{x^2 + 4x + 3}{x+3} = \displaystyle\frac{(x+1)(x+3)}{x+3} = x+1 \end{align\*}

If you tell a computer to evaluate $x^2+4x+3$ and then divide it by $x+3$, it will choke on your program when you let $x = -3$. But a mathematician would not get stuck on this point needlessly. He would realize that this is most likely irrelevant to the point you are trying to make, and that giving up and complaining about this minor issue will not help anybody. He'll *get what you mean* because he doesn't just follow you; he *understands* you. It's harder to fail when your reader is smart.
> 31 votes

# Answer
One issue that I think was not addressed in Yuval's answer, is that it seems you are comparing different animals.

Saying "the code is correct" is a semantic statement, you mean to say that the object described by your code satisfies certain properties, e.g. for every input $n$ it computes $n!$. This is indeed a hard task, and to answer it, one has to look beyond mere syntax. Your mathematical analogy for this is "is this proof correct", which is hardly fair, as the correct analogy should be "is this theorem true, and if so how can we prove it?". While the former is a syntactic statement which could be "easily" verified, the latter is much harder (its hardness can be formalized). Think about the most complicated code you have ever tried to come up with, and compare it to trying to prove Poincaré's conjecture (now theorem), this should give you different proportions.

Verifying semantic properties of programs is undecidable (Rice's theorem), and analogously, checking if a statement in first order predicate logic is true is also undecidable. The point is that there is no real difference in hardness from the way you are looking at the problems. On the other hand, we can reason about syntactic properties of programs (compilers), and this is analogous to the fact that we can verify proofs. Bugs (the code doesn't do what I want) are semantic, so you should compare them to their correct counterpart.

I will strengthen Yuval and say that entire fields grew with the motivation of writing mathematical proofs that can be written and verified in some formal system, so even the verification process is not at all trivial.
> 25 votes

# Answer
> What is so different about writing faultless mathematical proofs and writing faultless computer code that makes it so that the former is so much more tractable than the latter?

I believe that the primary reasons are **idempotency** (gives the same results for the same inputs) and **immutability** (doesn't change).

*What if a mathematical proof could give different results if it was read on a Tuesday or when the year advanced to 2000 from 1999? What if part of a mathematical proof was to go back a few pages, re-write a few lines, and then start again from that point?*

I'm sure that such a proof would be nearly as prone to bugs as a normal segment of computer code.

I see other secondary factors as well:

1. Mathematicians are usually far more educated before attempting to write a significant/publishable proof. 1/4 of self-titled professional developers started coding less than 6 years ago (see SO survey 2017), but I assume most mathematicians have over a decade of formal math education.
2. Mathematical proofs are rarely held to the same level of scrutiny as computer code. A single typo can/will break a program, but dozens of typos may not be sufficient to destroy a proof's value (just its readability).
3. The devil's in the details, and computer code cannot skip details. Proofs are free to skip steps which are deemed simple/routine. There are some nice syntactic sugars available in modern languages, but these are hard-coded and quite limited in comparison.
4. Mathematics is older and has a more solid foundation/core. There certainly is a plethora of new and shiny subfields in math, but most of the core principles have been in use for decades. This leads to stability. On the other side, programmers still disagree on basic coding methodology (just ask about Agile development and its adoption rate).
> 20 votes

# Answer
I agree with what Yuval has written. But also have a much simpler answer: In practice softwares engineers typically don't even try to check for correctness of their programs, they simply don't, they typically don't even write down the conditions that define when the program is correct.

There are various reasons for it. One is that most software engineers don't have the skills to clearly formulate problems mathematically nor they know how to write correctness proofs.

Another one is that defining correctness conditions for a complex software system (specially a distributed one) is a very difficult and time consuming task. They are expected to have something that seems to work in matter of weeks.

Another reason is that the correctness of a program depends on many other systems written by others which again so not have clear semantics. There is a Hyrum's law that essentially says if your library/service has an observable behavior (not part of its contract) someone will eventually depend on it. That essentially means the idea of developing software in modular form with clear contracts like lemmas in mathematics does not work in practice. It gets worse in languages in which reflection is used. Even if a program is correct today it might break down tomorrow when someone does some trivial refactoring in one of its dependencies.

In practice what typically happens is that they have tests. Tests act as what is expected from the program. Everytime a new bug is found, they add tests to catch it. It works to some extend, but it is not a correctness proof.

When people don't have the skills to define correctness nor write correct programs nor expected to do so and doing so is rather difficult it is no surprise that softwares are not correct.

But note also that at the end in better places software engineering is done by code review. That is the author of a program has to convince at least one other person that the program works correctly. That is the point some informal high level arguments are made. But again typically nothing close to a clear rigorous definition of correctness or proof of correctness happens.

In mathematics people are focused on correctness. In software development there are many things that a programmer needs to care about and there are trade offs between them. Having a bug-free software or even a good definition of correctness (with requirements changing over time) is an ideal, but it has to be traded off against other factors and one of the most important among them is time spent on developing it by existing developers. So in practice in better places the goal and processes are mitigating the risk of bugs as much as feasible rather than making the software bug-free.
> 13 votes

# Answer
I like Yuval's answer, but I wanted to riff off of it for a bit. One reason you might find it easier to write Math proofs might boil down to how platonic Math ontology is. To see what I mean, consider the following:

* Functions in Math are pure (the entire result of calling a function is completely encapsulated in the return value, which is deterministic and computed completely from the input value).
* Math doesn't have mutation or reassignment (when you need to model such things, functions and sequences are used).
* Math is referentially transparent (e.g. no pointers, no notion of call-by-name vs call-by-value) and Mathematical objects have extensional equality semantics (if "two" things are the same in every observable way, then they are in fact the same thing).

While it's arguable whether or not the above restrictions makes *writing* a program easier, I think there's broad agreement that the above restrictions do make *reasoning* about a program easier. The main thing you do when writing a Math proof is reason about the proof you're currently writing (since, unlike in programming, you never have to duplicate effort in Math as abstractions are free), so it's generally worth it to insist on the above restrictions.
> 12 votes

# Answer
There are a lot of good answers already but there are still more reasons math and programming aren't the same.

1 **Mathematical proofs tend to be much simpler than computer programs.** Consider the first steps of a hypothetical proof:

> Let a be an integer
>
> Let b be an integer
>
> Let c = a+b

So far the proof is fine. Let's turn that into the first steps of a similar program:

> Let a=input();
>
> Let b=input();
>
> Let c = a+b;

We already have a myriad of problems. Assuming that the user really did enter an integer, we have to check the bounds. Is *a* greater than -32768 (or whatever the min int on your system is)? Is *a* less than 32767? Now we have to check the same thing for *b*. And because we've added *a* and *b* the program isn't correct unless *a+b* is greater than -32768 and less than 32767. That's 5 separate conditions a programmer has to worry about that a mathematician can ignore. Not only does the programmer have to worry about them, he has to figure out what to do when one of those conditions isn't met and write code to do whetever he has decided is the way to handle those conditions. Math is simple. Programming is hard.

2 The questioner doesn't say whether he's referring to compile-time errors or run-time errors, but **programmers generally just don't care about compile-time errors.** The compiler finds them and they're easy to fix. They're like typos. How often do people type several paragraphs without errors the first time?

3 **Training.** From a very young age we are taught to do math, and we face the consequences of minor mistakes over and over again. A trained mathematician had to start solving multi-step algebra problems usually in middle school and had to do dozens (or more) such problems every week for a year. A single dropped negative sign caused an entire problem to be wrong. After algebra the problems got longer and more difficult. Programmers, on the other hand, usually have far less formal training. Many are self-taught (at least initially) and didn't get formal training until university. Even at the university level, the programmers have to take quite a few math classes while the mathematicians probably took one or two programming classes. It should hardly be surprising the even programmers tend to have decent math skills while mathematicians find it difficult to get a program right.
> 12 votes

# Answer
Fundamental mathematical proofs does not amount to a real world application, designed to meet live humans needs.

Humans will change their desires, needs, and requirements on what is possibly a daily basis in the realm of computer programs.

> What is so different about writing faultless mathematical proofs and writing faultless computer code that makes it so that the former is so much more tractable than the latter?

With as clear a requirement as a mathematical problem, a faultless program could be written. Proving that Dijkstra's algorithm can find the shortest path between two points on a graph is not the same as implementing a program that accepts arbitrary inputs and find the shortest points between any two points in it.

There are memory, performance, and hardware concerns to manage. I wish we could not think about those when writing algorithms, that we could use pure and functional constructs to manage this, but computer programs live in the "real" world of hardware whereas mathematical proof resides in... "theory".

---

Or, to be more succinct:
> 6 votes

# Answer
I can't find the reference, but I think Tony Hoare once said something along the following lines: The difference between a checking a program and checking a proof is that a proof can be checked two lines at a time.

In a word: locality.

Proofs are written so that they can be easily checked. Programs are written so that they can be executed. For this reason, programmers usually leave out information that would be useful to someone checking the program.

Consider this program, where x is read-only

```
    assume x >= 0
    p := 0 ;
    var pp := 0 ;
    while( x >= pp + 2*p + 1 )
    {
        var q := 1 ;
        var qq := q ;
        var pq := p ;
        while(  pp + 4*pq + 4*qq <= x )
        {
            q, pq, qq := 2*q, 2*pq, 4*qq ;
        }
        p, pp := p + q, pp + 2*pq + qq ;
    }
    assert  p*p <= x < (p+1)*(p+1)

```

It is easy to execute, but difficult to check.

But if I add back in the missing assertions, you can check the program locally by just checking that each sequence of assignments is correct with repect to its pre- and postconditions and that, for each loop, the postcondition of the loop is implied by the invariant and the negation of the loop guard.

```
    assume x >= 0
    p := 0 ;
    var pp := 0 ;
    while( x >= pp + 2*p + 1 )
        invariant p*p <= x
        invariant pp == p*p
        decreases x-p*p
    {
        var q := 1 ;
        var qq := q ;
        var pq := p ;
        while(  pp + 4*pq + 4*qq <= x )
            invariant (p+q)*(p+q) <= x
            invariant q > 0
            invariant qq == q*q
            invariant pq == p*q
            decreases x-(p+q)*(p+q)
        {
            q, pq, qq := 2*q, 2*pq, 4*qq ;
        }
        assert (p+q)*(p+q) <= x and pp==p*p and pq==p*q and qq==q*q and q>0
        p, pp := p + q, pp + 2*pq + qq ;
    }
    assert  p*p <= x < (p+1)*(p+1)

```

Coming back to the original question: Why is writing down mathematical proofs more fault-proof than writing computer code? Since proofs are designed to be easily checked by their readers, they are easily checked by their authors and thus alert authors tend not to make (or at least keep) logical errors in their proofs. When we program, we often fail to write down the reason that our code is correct; the result is that it is hard for both the readers and the author of a program to check the code; the result is that authors make (and then keep) errors.

But there is hope. If, when we write a program, we also write down the reason that we think the program is correct, we can then check the code as we write it and thus write less buggy code. This also has the benefit that others can read our code and check it for themselves.
> 5 votes

# Answer
Looking at it from another angle, in a non-academic setting it often comes down to money.

As the other posts assert well, Math is a single abstract specification, therefore a proof needs to work consistently within just that specification to be proven. A computer program may operate on many implementations of the abstract specification of math - that is to say the way one language, or hardware manufacturer implements floating point mathematics may be slightly different than another which may cause slight fluctuations in results.

As such, 'proving' a computer program before writing it would then involve proving the logic at the hardware level, operating system level, driver level, programming language, compiler, maybe interpreter and so on, for every possible combination of hardware that the program could conceivably be run on and any conceivable data it may ingest. You'll probably find this level of preparation and understanding on space missions, weapons systems or nuclear power control systems, where failure means tens of billions of lost dollars and potentially many lost lives, but not much else.

For your 'everyday' programmer and/or business, it is far, far more cost effective to accept a certain level of accuracy in mostly-correct code and sell a usable product, and the developers may retroactively fix bugs as they are uncovered during its usage.
> 4 votes

# Answer
I think that your reasoning is valid, but your input is not. Mathematical proofs simply aren't more fault-tolerant than programs, if both are written by humans. Dijkstra was already quoted here, but I will offer an additional quote.

> Yet we must organize the computations in such a way that our limited powers are sufficient to guarantee that the computation will establish the desired effect. This organizing includes the composition of the program and there we are faced with the next problem of size, viz. the length of the program text, and we should give this problem also explicit recognition. We should remain aware of the fact that the extent to which we can read or write a text is very much dependent on its size. \[...\]
>
> It is in the same mood that I should like to draw the reader's attention to the fact that "clarity" has pronounced quantitative aspects, a fact many mathematicians, curiously enough, seem to be unaware of. A theorem stating the validity of a conclusion when ten pages full of conditions are satisfied is hardly a convenient tool, as all conditions have to be verified whenever the theorem is appealed to. In Euclidean geometry, Pythagoras' Theorem holds for any three points A, B and C such that through A and C a straight line can be drawn orthogonal to a straight line through B and C. How many mathematicians appreciate that the theorem remains applicable when some or all of the points A, B and C coincide? yet this seems largely responsible for the convenience with which Pythagoras Theorem can be used.
>
> Summarizing: as a slow-witted human being I have a very small head and I had better learn to live with it and to respect my limitations and give them full credit, rather than to try to ignore them, for the latter vain effort will be punished by failure.

This is slightly edited last three paragraphs from first chapter of Dijkstra's Structured Programming.

To perhaps rephrase this, to apply better to your question: correctness is largely a function of size of your proof. Correctness of long mathematical proofs is very difficult to establish (lots of published "proofs" live in the limbo of uncertainty since nobody actually verified them). But, if you compare correctness of trivial programs to trivial proofs, there's likely no noticeable difference. However, automated proof assistants (in a broader sense, your Java compiler is also a proof assistant), let programs win by automating a lot of groundwork.
> 4 votes

# Answer
It's not. Mathematical proofs are exactly as buggy by nature, it's just that their readers are more permissive than a compiler. Similarly, the readers of a computer program are easily fooled into believing it is correct, at least until they try to run it.

For example, if we try to translate a mathematical proof into a formal language like ZFC, it will also contain bugs. That's because these proofs can get really long so we're forced to write a program to generate the proof. Few people go to the trouble, at their peril, although there is active research in formalizing foundational proofs.

And indeed, math can get BSOD! It wouldn't be the first time!

This orthodox idea that all mathematical proofs which have been sufficiently verified are essentially correct or can be made correct is the same one motivating your software project at work: as long as we stay on the roadmap, we'll get all the bugs out and the features complete — it's an iterative process leading to a definite final product.

Here's the flip side. Look, we've already got the funding, validated the business concept, all the documents are right here for you to read. We just need you to execute and it's a sure thing!

Let's not feel too sorry for Hilbert either, he knew what he was getting into. It's just business.

If you want to be really sure, take everything on a case-by-case basis and draw your own conclusions!
> 4 votes

# Answer
You should distinguish two different "categories":

* **pseudo-proofs** (or pseudo-code) - that is what you see in books. It is written in natural language (e.g. in English). That is what you should use to learn Math (or Algorithms).
* **formal proofs** (or formal code) - you write it when you need your proof (or code) to be mechanically verifiable (or executable). Such representation does not require any "human intelligence". It can be verified (or executed) mechanically, by following some predefined steps (usually done by computers today).

We have been using pseudo-code for thousands of years (e.g. Euclids algorithm). Writing formal code (in formal languages like C or Java) became extremely popular and useful after the invention of computers. But, sadly, formal proofs (in formal languages such as Principia Mathematica or Metamath) are not very popular. And since everybody writes pseudo-proofs today, people often argue about new proofs. Mistakes in them can be found years, decades or even centuries after the actual "proving".
> 4 votes

# Answer
We could ask whether it is more difficult in *practice*, or in *principle*, to write proofs or write code.

In practice, proving is much harder than coding. Very few people who have taken two years of college-level math can write proofs, even trivial ones. Among people who have taken two years of college-level CS, probably at least 30% can solve FizzBuzz.

But in *principle*, there are fundamental reasons why it's the other way around. Proofs can, at least in principle, be checked for correctness through a process that requires no judgment or understanding whatsoever. Programs can't -- we can't even tell, through any prescribed process, whether a program will halt.
> 3 votes

# Answer
As other answers have touched on in their answers(I want to elaborate), but a big part of the issue is library usage. Even with perfect documentation(as common as bugless code), it is impossible to transfer complete knowledge of a library to every programmer using the library. If the programmer doesn't perfectly understand their library, they may make mistakes when using it. Sometimes these may result in critical bugs that are discovered when the code doesn't work. But for minor bugs, these may go unnoticed.

A similar situation would be if a mathematician used existing proofs and lemmas without fully understanding them; their own proofs would likely be flawed. While this may suggest a solution is to perfectly learn every library one uses; this is practically very time consuming and may require domain knowledge the programmer doesn't have.(I know very little of DNA sequencing/protein synthesis; yet can work with these concepts using libraries).

More succinctly put, software engineering(engineering in general really) is based on encapsulating different levels of abstraction to allow people to focus on smaller areas of the problem they specialize in. This allows people to develop expertise in their area, but also requires excellent communication between each layer. When that communication isn't perfect, it causes problems.
> 3 votes

# Answer
I'll try to be original after all that great answers.

# Programs **are** proofs

The Curry–Howard isomorphism tells us, the types in your program are the theorems and the actual code is their proof.

Admittedly, this is a very abstract and high-level view. The issue you, probably, mean, is that writing a *typical* code is harder because it gets too low-level. In most cases you "need to tell the machine what to do". Or, to look into this from other way round: mathematicians are really good at abstraction.

As a side note: "The music of streams" is one of the most beautiful bridges between both. It basically sets up things to be able to say "I want *this* in *that* way" and the machine magically does *this* exactly as desired.
> 3 votes

# Answer
None of the many other answers point out the following. Mathematical proofs operate on imaginary computing systems which have infinite memory and infinite computing power. They can therefore hold arbitrarily large numbers to infinite precision, and lose no precision in any calculation.

Real world computers fall somewhat short of this ideal meaning implementing algorithms on them requires more thought and work. Proofs can contain symbols which represent things which cannot be contained in a real-world computer's memory, e.g. $\pi$.
> 3 votes

# Answer
I see two important reasons why programs are more error prone than math proofs:

1: Programs contain variables or dynamic objects changing over time, whereas mathematical objects in proofs are normally static. Thus, notation in math can be used as direct support of reasoning, (and if a = b, this remains the case) where this does not work in programs. Also, this problem gets far worse where programs are parallel or have multiple threads.

2: Math often assumes relatively neatly defined objects (graphs, manifolds, rings, groups, etc.) whereas programming deals with very messy and rather irregular objects: finite precision arithmetic, finite stacks, character-integer conversions, pointers, garbage that needs collection , etc... The collection of conditions relevant to correctness is therefore very difficult to keep in mind.
> 3 votes

# Answer
1. Computer programs are tested in the real world. A tricky technical error in a long mathematical proof, that only a limited number of people can understand, has a good chance of remaining undetected. The same sort of error in a software product is likely to produce strange behavior that ordinary users notice. So the premise might not be correct.
2. Computer programs perform useful real world functions. They don't have to be 100% correct to do this, and high standards of correctness are pretty expensive. Proofs are only useful if they actually prove something, so skipping the '100% correct' part is not an option for mathematicians.
3. Mathematical proofs are clearly defined. If a proof is flawed, the author has made a mistake. Many bugs in computer programs occur because the requirements weren't properly communicated, or there is a compatibility issue with something the programmer has never heard of.
4. Many computer programs cannot be proven correct. They might solve informally defined problems like recognizing faces. Or they may be like stock market prediction software and have a formally defined goal but involve too many real world variables.
> 2 votes

# Answer
A large portion of mathematics as a human activity has been the developing of domain-specific languages in which verification of proofs is easy for a human to do.

A proof's quality is inversely proportional to its length and complexity. The length and complexity is often reduced by developing good notation for describing the situation at hand about which we are making a statement, along with the auxiliary concepts interacting within the particular proof under consideration.

This is not an easy process, and most proofs witnessed by people removed from the forefront of research happen to be in mathematical fields (like algebra and analysis) that have had hundreds, if not thousands, of years during which the notation of that field has been refined to the point where the act of actually writing down the proofs feels like a breeze.

At the forefront of research though, particularly if you work on problems that are not in fields with well-established or well-developed notation, I would wager the difficulty of even a writing a correct proof approaches the difficulty of writing a correct program. This would be because you would also have to at the same time write the analog of a programming-language design, train your neural network to compile it correctly, try writing the proof in that, run out of memory, try to optimize the language, iterate your brain learning the language, write the proof again, etc.

To reiterate, I think that writing correct proofs can approach the difficulty of writing correct programs in certain areas of mathematics, but those areas are necessarily young and under-developed because the very notion of progress in mathematics is intimately tied up with the easy of proof verification.

Another way of phrasing the point I want to make is that both programming languages and mathematics are at the end of the day designed so that computer programs and proofs respectively are possible to compile. It's just that compiling a computer program is done in a computer and ensures syntactic correctness which has usually little to do with correctness of the program itself, while "compiling" a proof is done by a human and ensures syntactic correctness which is the same thing as correctness of the proof.
> 2 votes

# Answer
The domains of input vary greatly. Even in exotic cases, mathematical inputs are very rigorously defined so there is abundant clarity on what the inputs are. With computing the domain of inputs is so vast: a computer program can accept humble numbers (the simplest to verify) or touch input from a smart phone. The ever expanding appetite for digitisation, and by extension computability, implies continuously increasing complexity of software beyond the bounds of what can easily be verified. This need for digitisation strains our current abilities to 'keep up' leading to what we commonly refer to as 'bugs'.

Here's a quote from https://www.technologyreview.com/2002/07/01/40875/why-software-is-so-bad/ which illustrates this:

> “The classic dilemma in software is that people continually want more and more and more stuff,” says Nathan Myhrvold, former chief technology officer of Microsoft. Unfortunately, he notes, the constant demand for novelty means that software is always “in the bleeding-edge phase,” when products are inherently less reliable. In 1983, he says, Microsoft Word had only 27,000 lines of code. “Trouble is, it didn’t do very much”-which customers today wouldn’t accept. If Microsoft had not kept pumping up Word with new features, the product would no longer exist.
> 2 votes

# Answer
Only a small portion of mathematical statements which are true can be practically proven. More significantly, it would be impossible to construct a non-trivial(\*) set of mathematical axioms that would allow all true statements to be proven. If one only needed to write programs to do a tiny fraction of the things which could be done with computers, it would be possible to write provably-correct software, but computers are often called upon to do things beyond the range of what provably-correct software can accomplish.

(\*) It's possible to define a set of axioms which would allow all true statements to be enumerated, and thus proven, but those aren't generally very interesting. While it's possible to formally categorize sets of axioms into those which are or not, relatively-speaking, non-trivial, the key point is that the provable existence of statements which are true but can't be proven is not a flaw in a set of axioms. Adding axioms to make any existing true-but-unprovable statements provable would cause other statements to become true but without them provable.
> 1 votes

# Answer
You are honestly comparing apples and oranges here. **Fault-proof** and **bug-free** aren't the same thing.

If a program compares the numbers `2` and `3` and it says that `2 is greater than 3`, then it could be because of a buggy implementation:

```
# Buggy implementation
function is_a_greater_than_b(a,b):
  return b > a

```

The program is still fault free though. When comparing two numbers `a` and `b`, it will always be able to tell you if `b` is bigger than the `a`. It's just not what you (the programmer) were supposed to ask the computer to do.
> 1 votes

# Answer
a) Because computer programs are waaay bigger than math proofs

a.1) I believe that there's more people used during writting complex computer program than during writting math proof. It means that mistake margin is higher.

b) Because CEOs/Shareholders care more about money than fixing **small bugs**, meanwhile you (as developer) have to do your tasks to meet some requirements / deadlines / demos

c) Because you can be programmer without "deep" knowledge in comp sci, meanwhile it'd be hard to do in math ( I believe )

Additionally:

NASA:

> This software is bug-free. It is perfect, as perfect as human beings have achieved. Consider these stats: the last three versions of the program -- each 420,000 lines long - had just one error each. The last 11 versions of this software had a total of 17 errors.
>
> Take the upgrade of the software to permit the shuttle to navigate with Global Positioning Satellites, a change that involves just 1.5% of the program, or 6,366 lines of code. The specifications for that one change run 2,500 pages, a volume thicker than a phone book. The specifications for the current program fill 30 volumes and run 40,000 pages.

https://www.fastcompany.com/28121/they-write-right-stuff
> 0 votes

# Answer
# Basic Levels:

Let's look at things at the simplest, and most basic level.

For math, we have:
2+3=5

I learned about that when I was very, very young. I can look at the most basic elements: two objects, and three objects. Great.

For computer programming, most people tend to use a high-level language. Some high-level languages can even "compile" into one of the lower high-level languages, like C. C can then be translated into Assembly language. Assembly language then gets converted into machine code. A lot of people think the complexity ends there, but it doesn't: Modern CPUs take the machine code as instructions, but then run "micro code" to actually execute those instructions.

This means that, at the most basic level (dealing with the simplest of structures), we are now dealing with micro-code, which is embedded in the hardware and which most programmers don't even use directly, nor update. In fact, not only do most programmers not touch micro code (0 levels higher than micro code), most programmers don't touch machine code (1 level higher than micro code), nor even Assembly (2 levels higher than micro code) (except, perhaps, for a bit of formal training during college). Most programmers will spend time only 3 or more levels higher.

Furthermore, if we look at Assembly (which is as low level as people typically get), each individual step is typically understandable by people who have been trained and have the resources to interpret that step. In this sense, Assembly is much simpler than a higher level language. However, Assembly is so simple that performing complex tasks, or even mediocre tasks, is very tedious. Upper-level languages free us from that.

In a law about "reverse engineering", a judge declared that even if code can theoretically be handled one byte at a time, modern programs involve millions of bytes, so some sorts of records (like copies of code) must be made just for such an effort to be feasible. (Therefore internal development wasn't considered a violation of the generalized "no making copies" rule of copyright law.) (I'm probably thinking of making unauthorized Sega Genesis cartridges, but may be thinking of something said during the Game Genie case.)

# Modernization:

Do you run code meant for 286s? Or do you run 64-bit code?

Mathematics uses fundamentals that extend back for millennia. With computers, people typically consider investment in something two decades old to be uselessly wasteful of resources. That means Mathematics can be a lot more thoroughly tested.

# Standards of Used Tools:

I was taught (by a friend who had more formal computer programming training than myself) that there is no such thing as a bug-free C compiler that meets the C specifications. This is because the C language basically assumes the possibility of using infinite memory for the purpose of a stack. Obviously, such an impossible requirement had to be deviated from when people tried to make usable compilers that worked with actual machines that are a bit more finite in nature.

In practice, I have found that with JScript in Windows Script Host, I've been able to accomplish a lot of good using objects. (I like the environment because the toolset needed to try new code is built into modern versions of Microsoft Windows.) When using this environment, I've found that sometimes there is no easily-findable documentation on how the object works. However, using the object is so beneficial, that I do so anyway. So what I'd do is write code, which may be buggy as a hornet's nest, and do so in a nicely sandboxed environment where I can see the effects, and learn about the object's behaviors while interacting with it.

In other cases, sometimes only after I've figured out how an object behaves, I've found that the object (bundled with the operating system) is buggy, and that it is a known issue that Microsoft has intentionally decided will not be fixed.

In such scenarios, do I rely on OpenBSD, created by masterful programmers that create new releases on-schedule, on a regular basis (twice a year), with a famous security record of "only two remote holes" in 10+ years? (Even they have errata patches for less severe issues.) No, by no means. I don't rely on such a product with such higher quality, because I'm working for a business that support businesses that supply people with machines that use Microsoft Windows, so that is what my code needs to work on.

Practicality/usability require that I work on the platforms that people find useful, and that is a platform which is famously bad for security (even though tremendous improvements have been made from the early days of the millennium which the same company's products were much worse).

# Summary

There are numerous reasons why computer programming is more error prone, and that is accepted by the community of computer users. In fact, most code is written in environments which will not tolerate error-free efforts. (Some exceptions, such as developing security protocols, may receive a bit more effort in this regard.) Besides the commonly thought of reasons of businesses not wanting to invest more money, and miss artificial deadlines to make customers happy, there is the impact of the march of technology which simply states that if you spend too much time, you will be working on an obsolete platform because things do change significantly within a decade.

Offhand, I can recall being surprised at just how short some very useful and popular functions were, when I saw some source code for strlen and strcpy. For instance, strlen may have been something like "int strlen(char \*x){char *y=x;while (*(y++));return (y-x)-1;}"

However, typical computer programs are much lengthier than that. Also, a lot of modern programming will use other code which may be less thoroughly tested, or even known to be buggy. Today's systems are much more elaborate than what can easily be thought through, except by hand-waving away a lot of the minutia as "details handled by lower levels".

This mandatory complexity, and the certainty of working with complex and even wrong systems, makes computer programming a lot hardware to verify than a lot of mathematics where things tend to boil down to a lot simpler levels.

When you break things down in mathematics, you get to individual pieces that children can understand. Most people trust math; at least basic arithmetic (or, at least, counting).

When you really break down computer programming to see what's happening under the hood, you end up with broken implementations of broken standards and code that is ultimately executed electronically, and that physical implementation is just one step below microcode which most university-trained computer scientists don't dare touch (if they are even aware of it).

I've spoken with some programmers who are in college or recent graduates who outright object to the notion that bug-free code can be written. They've written off the possibility, and though they acknowledge that some impressive examples (which I have been able to show) are some convincing arguments, they consider such samples to be unrepresentative rare flukes, and still dismiss the possibility of being able to count on having such higher standards. (A much, much different attitude than the much more trustable foundation we see in math.)
> 0 votes

# Answer
Mathematical proofs describe "what" knowledge and programs describe "how to" knowledge".

Writing programs is more complex because the programmer has to reason about all the different states that can arise, and how the program's behavior changes as a result. Proofs use formulaic or categorical reasoning to prove things about other definitions.

Most bugs are caused by processes entering into states that the programmer did not anticipate. In a program you usually have thousands or, in a large system, millions of possible variables which are not static data, but actually transform the way program executes. All of these interacting together create behaviors which are impossible anticipate, especially in a modern computer where there are layers of abstraction changing underneath you.

In a proof, there is no changing state. The definitions and objects of discussion are fixed. Proving does require thinking about the problem generally and considering a lot of cases, but those cases are fixed by definitions.
> 0 votes

# Answer
There is a discussion over at crypto.stackexchange:

https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur

Basically, there is a proof that products of two large primes, as they are used in RSA, can be factored reasonably quickly. The proof is hard. There is no universal agreement on whether it is correct or not at this moment.

Now someone could implement a program following this proof, and try out if it can factor products of large primes quickly or not. This problem has the nice property that you can run the algorithm, it should succeed, and when it succeeds it is very easy to check that it found the correct solution.

So in the mathematical proof, it is possible that the proof is accepted even when it is completely wrong. And of course if it works in most but not all cases. The program doesn't have that luxury, if it doesn't work, it doesn't work. If it gets wrong results, that is easily found. That makes it easier to write mathematical proofs that *seem* correct because faults are harder to find. For mathematical proofs that *are* proven 100% correct vs. programs that *are* proven 100% correct, that's probably equally difficult.
> 0 votes

# Answer
Checking if a proof is error-free can be done in linear time. If the proof is a formal, it could be done with a computer.

Checking if a program has no bugs is Turing-hard. So it is undecidable.
> 0 votes

---
Tags: correctness-proof, mathematical-foundations, philosophy
---


# Question
Title: Is possible to have a "pointer" to a tree node in a functional language?
Suppose I have the following structure definition in C:

```
struct node {
    int value;
    struct node *parent, *left, *right;
}

```

If I want to represent a specific node inside a tree, all I need is a pointer to such node, which allows me to traverse the tree using the parent and children's link.

Instead, if I have a simple tree structure in a functional programming language, for example in Haskell

```
Data TreeNode a = Nil | Node a (TreeNode a) (TreeNode a)

```

is there a way to represent the concept of a node, which allows to explore the tree "locally"?

The question arises from approaching the lowest common ancestor problem, since I don't know even how to define the problem in a functional setting: what does it mean "taking in input two nodes"? Should one use a different tree representation?

# Answer
You are looking for the zipper data structure.
> 5 votes

---
Tags: terminology, trees, functional-programming, tree-traversal
---


# Question
Title: Algorithm to compute cheapest path between two pixels in an image
I need to compute the cheapest path between two pixels in an image. The travel cost is specified by the user, and may depend on the distance between the pixels (including pixel values, which is treated as an elevation), as well as other factors. I tried Dijkstra, by scaling coordinates by a factor so I can have more search directions, but for any reasonable sized image, it becomes horrible expensive. I need more search directions because otherwise, paths may have the same lengths that should not have the same length.

A continuous model would look like, find $r$ such that

$$ \int\_a^b f(\vec{r}(t))\\,\mathrm{d}t $$

is minimized, where $f$ is the image.

Notes:

* The image size can be large, 4096x4096
* The pixel values are floating point values. This makes any hash table based on pixel values infeasible
* It is sufficient to find *one* optimal (or approximately) optimal path

# Answer
> 2 votes
That sounds like a variant of grid pathfinding(mostly used in game).

Generally, if your cost function has a good heuristics, A star will give you an optimal solution with least time cost. But space waste is serious, so you can try Fringe Search. This article gives a lot of good search algorithms.

But, if cost is literally a mess, best search algorithm is definitely Dijkstra(additionally, any cost must be \>= 0, otherwise it's SPFA).

Another direction is tolerating some suboptimality. I searched a lot, and because games' maps are basically mirrors of real world, so many researches are based on uniform-cost. So here is some of my personal suggestion:

You can run depth-limit DFS to find an optimal node in given range and run DFS again on that node, until you reach the optimal. This is a simple greedy search(without heuristics). You must store visited node to avoid infinite loop.

Another way is running BFS first to reach target, and then try to *trim path*. The complexity varies based on your evaluating function. Firstly, based on your cost function, customize a evaluating funtion to select some "station"(like railway system), and then run search algorithm on each $(s\_i,s\_{i+1})$.

Here is a good overview Fast-Grid based Path Finding for Video Games

I am not sure if it's worth to solve a calculus optimization problem (which ignore grid topology structure!). So I only provide these "traditional" CS approaches. Hope this help you.

---
Tags: optimization, shortest-path
---


title: regex find substring matches in text

text:
# Question
Title: regex find substring matches in text
I have written a regex engine and it can match whole strings to a pattern without a problem, i.e.: `match(E, w)` and it returns `true` or `false` if the string $w$ matches the expression $E$ or not. But I was thinking of how to extend the matching function to find substrings in a string that match an expression. The obvious solution is the one I came up with - go through all substrings of the given string and test them against the expression. This is obviously pretty slow since the number of substrings for a string $w$ will be $\frac{|w|(|w| + 1)}{2}$ and even though the matching function has $O(n)$ complexity the extended matching function will be $O(n^3)$. I tried googling around but no actual algorithm describing how this kind of thing would work popped up. So I am asking here...

P.S. I also thought of a way to determine lower and upper bounds for the length of words in the language that a given expression describes but that would only marginally improve the algorithm even if you don't use the star operator.

# Answer
One approach is to match against the regexp `.* E .*`, then figure out how it matches. Whether you can figure out how that matched depends on the algorithm you are using to implement `match`. This will look for one substring that matches, not all of them.
> 0 votes

---
Tags: regular-expressions
---


# Question
Title: Why does the formula floor((i-1)/2) find the parent node in a binary heap?
I learned that when you have a binary heap represented as a vector / list / array with indicies \[0, 1, 2, 3, 4, 5, 6, 7, 8, ...\] the index of the parent of element at index i can be found with parent index = floor((i-1)/2)

I have tried to explain why it works. Can anyone help me verify this?

Took reference from Why does the formula 2n + 1 find the child node in a binary heap? thanks to @Giulio

# Answer
Levels by levels, the indexes of a binary heap are

$$0\\1\ \ \ \ \ \ \ \ \ \ \ \ \ 2\\3\ \ \ \ \ \ 4\ \ \ \ \ \ 5\ \ \ \ \ \ 6\\7\ 8\ 9\ 10\\,11\\,12\\,13\\,14\\\cdots$$

and it is rather clear that the sons of $n$ are $2n+1$ and $2n+2$.

By inversion, the father of $m$ is one of $\dfrac{m-1}2$ or $\dfrac{m-2}2$, and more precisely the one that is an integer.
> 2 votes

# Answer
Let's assume that each tier of the heap is an array.

```
T1 [                n0                 ]

T2 [      n1,                n2        ]

T3 [  n3,     n4,       n5,       n6   ]

T4 [n7, n8, n9, n10, n11, n12, n13, n14]

```

It may not be clear, but I want you to imagine that $n0$ is the parent of $n1$ and $n2$.

Likewise, $n1$ is the parent of $n3$ and $n4$.

For example, the second tier's length is $2$.

i.e. $\[n1, n2\]$

Let's say $i$ is the global index of the node in question (i.e. the node's index if the entire tree were to be collapsed within a single array), and $j$ is the local index of the node, i.e. the index of the node within its tier.

e.g. In the diagram above, if the node in question is $n3$, $i$ is $3$ and $j$ is $0$, because $n3$ is the first element in the 3rd tier.

```
i = global index of a node n
j = local index of a node n within the tier where the node exists
T = tier

```

The maximum number of nodes in a certain tier can be expressed by:

$2^T - 1$ // e.g. when you have 3 tiers, you can have at most 7 nodes, as $2 \cdot 2 \cdot 2 - 1 = 7$

This is because there are $2^{T-1}$ nodes in each tier (note: tier numbering in our example arbitrarily starts from $1$, not $0$) and the sum of powers of $2$ up to $n$ is equal to $2^{n+1} - 1$, as you can see here https://math.stackexchange.com/questions/1990137/the-idea-behind-the-sum-of-powers-of-2

This means that the global index of the last node in the tier is:

$i\_{last} = 2^T-1-1$

While the local index of the last node in the tier is:

$j\_{last} = 2^{T-1} - 1$ // since there are $2^{T-1}$ elements in tier $T$

We can now compute the global index of the first node in the tier by subtracting the local index of the last node in the tier from its global index:

$i\_{first} = i\_{last} - j\_{last}$

$i\_{first} = 2^T - 1 - 1 - j\_{last}$

$i\_{first} = 2^T - 1 - 1 - (2^{T-1} - 1)$

$i\_{first} = 2^T - 2^{T-1} - 1$

$i\_{first} = 2\*2^{T-1} -2^{T-1} - 1$

$i\_{first} = (2 - 1)\*2^{T-1} - 1$

$i\_{first} = 2^{T-1} - 1$

We can now compute the global index of a node $n$ by adding its local index and the global index of the first node in its tier:

$i = i\_{first} + j$

$i = 2^{T-1} - 1 + j$

Let's now think about the parent of the node in question.

```
The parent, n', will be in the previous tier, T-1.
The indices in T-1 will be referred to as i', j', i'_first ...

```

Based on what we've shown so far, we can say that the global index of the parent node in the previous tier is:

$i\_{first}' = 2^{T-1-1} - 1$

Now, for every 2 predecessor(left sibling) of the node $n$ in tier $T$ there will be 1 predecessor(left sibling) of parent node $n'$ in $T-1$. Also, given index $j$ in $T$, we know there are $j$ predecessors(left sibling) of $n$ in $T$ \- i.e. the index of a node is equal to the number of its predecessors(left sibling). So we can conclude that:

$j' = floor(j/2)$

Putting it all together, we can conclude that

$i' = i\_f' + j'$

$i' = 2^{T-1-1} - 1 + floor(j/2)$

Now let's rework the previous equation for the global index of parent node $n$, $i = 2^{T-1}-1+j$ to the following:

$i + 1 = 2^{T-1} + j$

Finally, let's compare that to the equation of the global index of the left-child node:

$\begin{align} i' &= 2^{T-1-1} - 1 + floor(j/2)\\ &= 2^{T-1}/2 + floor(j/2) - 1\\ &= floor((2^{T-1} + j)/2) - 1\\ &= floor((i + 1)/2) - 1 \text{//NOTE: Here we use $i + 1 = 2^{T-1} + j$ mentioned above}\\ &= floor((i - 1)/2)\\ \end{align}$
> 0 votes

# Answer
If you look at the indices of nodes in a binary heap, left child index is always an odd number, and right is always even.

e.g.

```
# I made the values match the indices for simplicity
[0,1,2,3,4,5,6]

   0
  / \
 1   2
/ \ / \
3 4 5 6

```

For parent `1`, left is index `3` and right is index `4` (odd and even). Similarly, for parent `2`, left is `5` and right is `6` (odd and even).

Formulae for the left and right children are (assume `i` is the index of the parent node):

```
left = 2 * i + 1
right = 2 * i + 2

```

Using simple algebra, we can say that `i = (left - 1) / 2 = (right - 2) / 2`:

```
left = 2 * i + 1
left - 1 = 2 * i + 1 - 1
left - 1 = 2 * i
(left - 1) / 2 = i

right = 2 * i + 2
right - 2 = 2 * i + 2 - 2
right - 2 = 2 * i
(right - 2) / 2

```

So we have two formulae for computing the parent from either the left or the right child. We also know that right is always even. This means `right - 1` will always be odd, and that dividing it by 2 will result in some fraction as opposed to a whole number. Therefore, we can apply the formula for getting the left child's parent to the right child as long as we get the floor of `(right - 1) / 2`. It'll work for the left child because the floor of a whole number is the whole number itself. It'll also work for the right child because the floor of a fraction is just its lower bound.
> 0 votes

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


# Question
Title: Prove that $\texttt{prefix}(L)$ is regular
Given that $L = \lbrace 0^n1^n : n \geq 0\rbrace$ is a non-regular context-free language, prove that $\texttt{prefix}(L)$ is regular.

So far I have provided that the grammar to produce this language is: $S \rightarrow 0S1 \thinspace | \thinspace \epsilon$

Would you go about proving $\texttt{prefix}(L)$ is regular just like you would any language, proving that $\Sigma^\star$ = $\texttt{prefix}(L)$, or by induction on the length of the words in $\texttt{prefix}(L)$.

# Answer
> 3 votes
It appears that $prefix(L)$ is non-regular.

Let $L = \\{0^n 1^n: n \ge 0\\}$. Then, $prefix(L)$, defined to be the set of all prefixes of strings in $L$, is the set of all strings that consist of zero or more $0$'s followed by at most the same number of $1$'s, i.e. $prefix(L) = \\{0^n 1^m: m \le n\\}$. Intuitively, the reason $prefix(L)$ is nonregular is that a machine that can check whether the number of $1$'s does not exceed the number of $0$'s must store a count of the number of $0$'s in the input seen so far, and so this language cannot be recognized by a machine with a finite number of states.

A formal proof that $L' := prefix(L)$ is nonregular is as follows. Consider the subset $S = \\{0^1, 0^2, \ldots, 0^p\\}$. Any DFA $M$ that recognizes $L'$ must take the inputs $0^i$ and $0^j$ $(i \< j)$ to different states because $0^i 1^j \notin L'$ but $0^j 1^j \in L'$. Hence, the machine $M$ contains at least $p$ states. But $p$ was arbitrary. This proves there does not exist a DFA (with a finite number of states) recognizing $L'$.

This proof method requires us to find an infinite subset $S$ of pairwise distinguishable prefixes; see online about the Myhill-Nerode theorem.

# Answer
> 0 votes
The language $\textrm{prefix}(L) = \\{0^n1^m:n \geq m\\}$. It's not regular.

From the pumping lemma:

> Let $L$ be a regular language. Then there exists an integer $p \geq 1$ depending only on $L$, such that every string $w \in L$, of length at least $|w| \geq p$ ( $p$ is called the "pumping length") can be written as $w = x \cdot y \cdot z$(i.e., $w$ can be divided into three substrings), satisfying the following conditions:
>
> * $|y| \geq 1$
> * $|xy| \leq p$
> * $\forall n \geq 0 : xy^nz \in L$

Let's create a word $0^p1^p$. Since $|xy| \leq p$, than the substring of $w$, that we will be pumping has to be wholly within first $p$ characters, meaning that it can consist only of $0$-es.

However, $w = xy^0z \notin L$, since it would contain less $0$-es than $1$-s

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


title: Number of equivalence classes in $P$

text:
# Question
Title: Number of equivalence classes in $P$
I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $\Sigma^\*$ and $P - \\{\phi,\Sigma^\*\\}$. I am unable to figure out how this is true, specifically how if $L\_1,L\_2 \in P, L\_1 \sim\_P L\_2$. I think there's a simple fact/idea I am missing out on, but I don't know what it is.

# Answer
Suppose that $L\_1 \in \mathsf{P}$ and $L\_2$ is non-trivial. Pick $y \in L\_2$ and $z \notin L\_2$ arbitrary. The following is a polynomial time reduction from $L\_1$ to $L\_2$:

* Input: $x$.
* Check whether $x \in L\_1$.
* If so, output $y$.
* Otherwise, output $z$.

This runs in polynomial time since $L\_1 \in \mathsf{P}$.
> 2 votes

# Answer
The existing answer is good, but doesn't tackle the empty and full languages and also leaves some doubts unspecified. I'll solve the full question.

---

First, let's be clear about our definitions: $L\_1 \leq\_p L\_2$ when there is a *polynomial-time mapping reduction* from $L\_1$ to $L\_2$. That is, there is a function $f(x)$ from $L\_1$ to $L\_2$ so that

1. it is a mapping reduction, i.e. $x\in L\_1 \Leftrightarrow f(x)\in L\_2$, and
2. $f(x)$ is computable in $O(p(|x|))$, with $p$ some polynomial.

Polynomial equivalence $L\_1 \sim\_p L\_2$ holds when $L\_1 \leq\_p L\_2$ and $L\_2\leq\_p L\_1$.

$P$ is the class of languages where each word $x$ can be decided to be in the language within $O(p(|x|))$, where $p$ is a polynomial once again.

---

Consider two languages $L\_1$ and $L\_2$ in $P\setminus\\{\emptyset,\Sigma^\*\\}$. We have a budget of $O(p(|x|))$ time for an $f$ to map every word *in* $L\_1$ to a word *in* $L\_2$, and words *out of* $L\_1$ to a word *out of* $L\_2$. We perform the reduction as follows for a given $x$. (This is an extension of the existing answer.)

1. Decide whether $x\in L\_1$. This takes a polynomial amount of time in $|x|$, so our budget is not exceeded.
2. Find a string $a\in L\_2$ and a string $b\notin L\_2$.
    * Wait, but how? What if it takes a long time to find those strings? Yes, that's possible. *But it doesn't exceed our budget!* Why? Because the time needed to search for a fitting $a$ and $b$ -- for example by randomly checking strings -- is *independent of $|x|$*. It is $O(1)$ from the perspective of the size of our input -- so are the checks by the way, since they are polynomial in $|a|$ and $|b|$ and independent of $|x|$ -- and hence this is also a polynomial-time step!
3. If $x\in L\_1$ was true, set $f(x)=a$, else $f(x)=b$.

We never exceeded our polynomial budget, and we successfully found a mapping reduction, so $L\_1 \leq\_p L\_2$. You can swap around $L\_1$ and $L\_2$ and hence find $L\_1 \sim\_p L\_2$.

---

Why are $\emptyset$ and $\Sigma^\*$ different (both are decidable in $O(1)$ and hence they both live in $P$ too)? That's easy: if you use $\emptyset$ as $L\_2$, then step 2 can't find an $a$. Thus, for all languages $L\_1\in P\setminus\\{\emptyset,\Sigma^\*\\}$, we have $L\_1 \not\leq\_p L\_2$. But there is one $L\_1$ language that can cope with the lack of $a$ in $L\_2$: that's $\emptyset$ itself, because it never needs an $a$ since it rejects all strings! It's also clear that $\Sigma^\*$ clearly cannot be reduced to $\emptyset$, because it accepts all strings and hence definitely needs an $a$ in $\emptyset$, so $\emptyset \not\sim\_p \Sigma^\*$. So, $\emptyset$ is an equivalence class by itself.

The same argument holds for $\Sigma^\*$, but for finding a $b$ instead of an $a$. It is also an equivalence class by itself.

---

Conclusion: the equivalence relation $\sim\_p$ partitions $P$ into exactly 3 equivalence classes: $\\{\emptyset\\}, \\{\Sigma^\*\\}, P\setminus \\{\emptyset,\Sigma^\*\\}$.
> 2 votes

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


# Question
Title: A lower bound for the makespan of heterogenous fog nodes
Why there is a sigma in the denominator of equation (8) in the picture? suppose we have n tasks and m fog nodes.

# Answer
Under the assumption that $EXT(N\_i) = \mathit{MinMakespan}$, $$ \sum\_{k \in N\_i \mathit{Tasks}} \mathit{length}(T\_k) = \mathit{MinMakespan} \times \mathit{CPUrate}(N\_i). $$ Therefore $$ \sum\_k \mathit{length}(T\_k) = \sum\_i \sum\_{k \in N\_i \mathit{Tasks}} \mathit{length}(T\_k) = \sum\_i \mathit{MinMakespan} \times \mathit{CPUrate}(N\_i) = \\ \mathit{MinMakespan} \times \sum\_i \mathit{CPUrate}(N\_i). $$ It follows that $$ \mathit{MinMakespan} = \frac{\sum\_k \mathit{length}(T\_k)}{\sum\_i \mathit{CPUrate}(N\_i)}. $$
> 1 votes

---
Tags: optimization, combinatorics, distributed-systems, scheduling, modelling
---


# Question
Title: Any-goal bidirectional A* pathfinding reference
I want to solve the problem of finding a shortest path on a directed weighted graph from a certain node to *any* of a specified set of destination nodes (preferably the closest one, but that's not that important). The standard (I believe) way to do this with the A\* algorithm is to use a distance-to-closest-goal heuristic (which is admissable) and exit as soon as any of the goal nodes is reached.

However, in my scenario (which is game AI, if that matters) some (or all) of the goals might be unreachable; furthermore, the set of nodes reachable from such goals is typically quite small (or, at least, I want to optimize in that particular case). For the case of a single goal, bidirectional search sounds promising: the reverse search direction would quickly exhaust all reachable nodes and conclude that no path exists. These slides by Andrew Goldberg et al. describes the bidirectional A\* algorithm with proper conditions on the heuristics, as well as stopping conditions.

My question is: is there a way to combine these two approaches, i.e. to perform bidirectional A\* to find path to *any* of a specified set of goal nodes? I'm not sure what heuristic function to choose for the reverse search direction, what are the stopping conditions, etc.

# Answer
It is definitely possible to make a bidirectional graph search algorithm with several possible destinations. Simply add all the destination nodes to the destination-search priority queue, all of them with weight 0. The backward search will start from all the destinations at once, instead of just starting from a single one.

In short, when you're initializing your priority queues and your empty set, use:

src_seen = set()
dst_seen = set()

src_prio_queue = heapify([(0, src)])
dst_prio_queue = heapify([(0, dst1), (0, dst2), (0, dst3), ...])

while src_prio_queue and dst_prio_queue:
    ...  # regular bidirectional A*
```

> 2 votes

---
Tags: reference-request, shortest-path, a-star-search
---


title: Exotic closure of regular languages

text:
# Question
Title: Exotic closure of regular languages
Let $L\_1 \subseteq \\{0,1\\}^{\*}$ be a regular language, and let $L\_2 \subseteq \\{0,1\\}^{\*}$ be some (not necessarily regular) language. Show that $$L=\left\\{ \sigma\_{1}\\#\sigma\_{2}\dots\\#\sigma\_{n}\mid\substack{n\geq1\\ \sigma\_{i}\in\left\\{ 0,1\right\\} \\ \exists w\_{1},\dots w\_{n-1}\in L\_{2}\quad\sigma\_{1}w\_{1}\sigma\_{2}w\_{2}\dots w\_{n-1}\sigma\_{n}\in L\_{1} } \right\\} $$ is regular.

I tried thinking about the Myhill–Nerode classes, and about closure under homomorphism, and homomorphism inverse, but I didn't achieve any result. I also tried thinking about $L\_1$'s DFA and trying to squeeze NFA in between edges, but I don't have an NFA for L2...

# Answer
Because of the choices for $w\_i$, it is easier to track the conditions if we include non-determinism.

---

Let $L\_1$ be accepted by DFA $D=(Q, \\{0,1\\}, \delta, q\_0, F)$.

Let NFA $N=(Q\sqcup Q\_\\#\sqcup\\{\text{dead}\\}\\}, \\{0,1,\\#\\},\tau, (q\_0)\_\\#, F)$, where

* $Q\_\\#$ is a $\\#$-tagged copy of $Q$, i.e., $Q\_\\#=\\{q\_\\#\mid q\in Q\\}$.
* For all $\sigma\in\\{0,1\\}$ and for all $q\in Q$,
$\tau(q\_\\#, \sigma) =\\{\delta(q, \sigma) \\}$,
$\tau(q, \\#) = \\{r\_\\# \mid \exists w\in L\_2 \text{ such that } \delta(q, w )=r\\}$, and
$\tau(q\_\\#, \\#)=\tau(q, \sigma)=\tau(\text{dead}, \sigma)=\tau(\text{dead}, \\#)=\\{\text{dead}\\}$.

In plain words, when it is running against an input, for each executing path, $N$ will either alternate its state between tagged states and nontagged states, ending up in $F$ possibly, or go into state $\text{dead}$, a trapped state. In particular, when $N$ in an untagged state reads a $\\#$, it can move to any corresponding tagged state as if it were $D$ reading any word in $L\_2$.

It is a routine exercise to verify the regular language accepted by $N$ is $L$. So $L$ is regular.
> 2 votes

---
Tags: regular-languages, closure-properties
---


title: DFA and NFA with 2 Substrings

text:
# Question
Title: DFA and NFA with 2 Substrings
I am preparing for my CS exam and found this question in a collection of old exams:

> Find a DFA and NFA with Σ = {o,p,q} that checks if the substrings op and pq are present in the string.

I thought, I understood this topic, but I can not find a regular expression for this problem.

My initial thought was `{o ∪ p ∪ q ∪ op+ ∩ pq+}*` but that seems wrong to me. Can anyone give me a clue or answer, so I can understand this and develop the automatons by myself?

Another idea was `{o ∪ p ∪ q}* {opq ∪ pqop}+ {o ∪ p ∪ q}*`, but that seems too 'hard coded' for me.

# Answer
Find an automaton for $L\_1= \\{uopv\mid u,v\in \Sigma^\*\\}$ and an automaton for $L\_2 = \\{upqv\mid u,v\in\Sigma^\*\\}$ (this should be easy enough).

Then, you can compute the product automaton of the two languages, accepting $L\_1\cap L\_2$.
> 3 votes

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


# Question
Title: Naïve array sampling algorithm: the possibility of a item being chosen and its time complexity
This naïve sampling algorithm I am talking about is fairly simple: create a set for storing chosen items first, randomly select an item from the array, and examminate if it is in the set. If it isn't, add it to the set, otherwise we will skip and reselect. This process will be repeated until required amount of samples are seccessfully selected.

Following is the JavaScript version of the algorithm (fell free to paste it into a browser console and try it):

```
function sample(arr, n) {
    if (n >= arr.length) return arr.slice(0);

    let set = new Set();
    while (set.size < n) {
        let index = Math.floor(Math.random() * arr.length);
        if (set.has(index)) continue;
        else set.add(index);
    }

    let result = [];

    for (let index of set) {
        result.push(arr[index]);
    }

    return result;
}

```

Although is simple, it is difficult for me to find out the time complexity, and the possibility for each array items to be chosen. If the algorithm is practical, it should garentee every items has equally $k/N$ possibility to be selected, when we select $k$ items from an array with $N$ items. Unfortunately, I cannot prove this.

The time complexity is hard to handle with too, because the algorithm is based on random selecting, so it is possible that we happen to select the same item for many times, and as more and more items are selected, this possibility will increase, which makes the time complexity harder to compute.

# Answer
> 1 votes
Assume that $m$ items have already been chosen. The next one needs to be different, which occurs with probability $1-\dfrac mn$. So the expectation of the number of drawings is $\dfrac{n}{n-m}$ (geometric law). To reach the quorum of $k$ numbers, you will need

$$\sum\_{m=0}^{k-1}\frac n{n-m}=n\left(H\_{n}-H\_{n-k}\right)\sim n\log\frac n{n-k}\\\sim k\ \text{ if }k\ll n$$ drawings on average, each corresponding to a search in the current set. To this, you add $k$ insertions.

You cannot do much better than assuming constant time for searches and insertions with a hash table.

---
Tags: algorithms, randomness, statistics, sampling
---


# Question
Title: Efficient algorithm to count number of intersections of n sets
I've come across this problem when working on a personal project of mine. I need an efficient algorithm of counting the number of overlaps between all pair combinations of n sets.

Example:

Set a = \[adam, ben, charlie, ...\]

Set b = \[adam, john, kenny, ...\]

Set c = \[adam, john, eve, ...\]

...

Set n

The algorithm will then get all pair combinations of sets, and count the number of intersections within those pairs.

e.g.

Set a & b = 1 (adam is in both sets)

Set a & c = 1 (adam is in both sets)

Set b & c = 2 (adam and john is in both sets)

...

The naïve algorithm I have come up with is:

1. Generate all 2-combinations of the sets and put them in a list.
2. For each pair in the list, find the intersection of the pair, add the count to the result list
3. Repeat for all pairs

Each set can have over 10k elements (strings), and there are over 1k sets. Obviously the performance is horrible since the runtime is exponential.

Are there any methods to improve the runtime? Is there a different algorithm that would improve the calculation? The results doesn't have to be exact, i.e. it can be an estimation.

Edit:

The task is to find overlapping users from different communities. For example we have different communities 1, 2, 3, etc. each community has their users (usernames in the list). I am trying to find the number of overlapping users from each community. e.g. community 1 shares 200 users with community 2, shares 400 users with community 3, so on and so forth.

# Answer
Assuming you really need the number for all pairs of sets and hearing that we are thinking of users in communities you could use the following algorithm which relies on the idea that the the average number of sets/communities a user is part of $k$ is much smaller that the number of total sets $k \<\< n$. Let $m$ refer to the total number of unique users.

Now:

```
// build a reverse index as described in the comments
// this takes  $O(n + km)$ because every user is in $\approx k$ sets
reverse_index := new HashMap()

for i = 0, ..., sets.length-1:
    S := sets[i]
    for key in S:
        if key not in reverse_index:
            reverse_index[key] = new List()
        reverse_index[key].append(i)

// create a n x n array for out final results $O(n^2)$
results := int[n][n]
for i = 0,...,n-1:
    for j = 0,...,n-1:
        results[i][j] = 0

// go through every user and connect all the sets they are in $O(mk^2)$
for key in reverse_index:
    L := reverse_index[key]
    k := L.length
    for i = 0,...,k-1:
        for j = i+1,...,k-1:
            // each user is in $k$ sets
            // so we need to add $k^2$ "connections"
            results[L[i]][L[j]] += 1
            results[L[j]][L[i]] += 1

```

The total runtime is $O(n^2+mk^2)$. The worst case occurs if $k \approx n$ \- as mentioned all ready all of this is based on a heuristic. Also make sure that you use an integer user id to identify users and not strings, as computing the hashes of string is additional overhead.
> 1 votes

---
Tags: algorithms, graphs, optimization, sets
---


# Question
Title: how can I fix my SQL for loop so that the index is not out of bounds?
I want to create a table that has the following results:

```
id  | field1 | field2
1   |   1    |   1
2   |   2    |   2
3   |   3    |   3
4   |   4    |   4
5   |   1    |   2
6   |   2    |   3
7   |   3    |   4
8   |   4    |   1
9   |   1    |   3
10  |   2    |   4
11  |   3    |   1
12  |   4    |   2
13  |   1    |   4
14  |   2    |   1
15  |   3    |   2
16  |   4    |   3

```

so basically it contains all possible pairs of numbers from 1 to 4. This is what I have so far:

```
DECLARE
  i2 NUMBER := 1;
BEGIN

FOR v_LoopCounter IN 1..3 LOOP
    FOR w_LoopCounter IN 0..3 LOOP

        INSERT INTO MY_TABLE (ID, FIELD1, FIELD2)
            VALUES (TO_CHAR(i2),TO_CHAR(w_LoopCounter+1),TO_CHAR(w_LoopCounter+v_LoopCounter));
           i2 := i2 + 1;

    END LOOP;
END LOOP;
COMMIT;
END;

```

but it produces wrong results, the field2 is out of range in further cases:

```
id  | field1 | field2
1   |   1    |   1
2   |   2    |   2
3   |   3    |   3
4   |   4    |   4
5   |   1    |   2
6   |   2    |   3
7   |   3    |   4
8   |   4    |   5  <-- here is a bad value
9   |   1    |   3
10  |   2    |   4
11  |   3    |   5  <-- here is a bad value
12  |   4    |   6  <-- here is a bad value, etc.
13  |   1    |   4
14  |   2    |   5
15  |   3    |   6
16  |   4    |   7

```

how can I adjust my code so that it focuses only a specific range and loops through it?

Thanks!

# Answer
If the order of the values is not important, you could simply do:

```
id = 1
for i = 1 to 4 do
    for j = 1 to 4 do
        INSERT(id, i, j)
        id += 1

```

If you want the exact same order as stated in your question, I think this is a solution:

```
id = 1
for i = 1 to 4 do
    for j = 1 to 4 do
        k = (i + j - 2) mod 4 + 1
        INSERT(id, j, k)
        id += 1

```
> 1 votes

---
Tags: algorithms, loops
---


# Question
Title: n points in 2d plane and a method(a,b) that returns all points closer to 0 than (a,b)
Given n points in a 2d plane I.E $ (x\_1,y\_1),(x\_2,y\_2)\dots (x\_n,y\_n) $.

Create a data structure that holds the points and a method closer$(a,b)$ that returns all the points in the data structure that are closer to $(0,0) $ than to $(a,b) $.

The preprocessing and creation of the data structure have no complexity limit but the closer$(a,b)$ has a time complexity of $\mathcal{O}(\log(n)+k)$ where n is the number of points and k is the amount of points closer to $(0,0)$ .

I'm quite certain it involves self balancing binary search trees, but not sure how to implement it. If $(a,b)$ is given during preprocessing then we can just make an array and sort it with $$d=(x\_i-0)^2+(y\_i-0)^2-((x\_i-a)^2+(y\_i-b)^2)$$. That would give us a search in $\log(n)$ on the first element in the array that is bigger than $ 0 $ and then we can just run a for loop j times.

If (a,b) is not given during preprocessing then I don't know how to approach this, I tried switching to polar coordinates or trying to find the mathematical Locus but It didn't seem to get me anywhere.

# Answer
> 7 votes
This is equivalent to finding all the points in a query half-plane, which has a cute, non-obvious solution in terms of convex layers, using fractional cascading to speed up moving from layer to layer.

---
Tags: data-structures
---


# Question
Title: If inorder traversal of a tree is in ascending order will the tree definitely be a BST?
For a binary search tree (BST) the inorder traversal is always in ascending order. **Is the converse also true?**

# Answer
> 12 votes
Yes.

The proof is straightforward. Assume you have a tree with a sorted in-order traversal, and assume the tree is not a BST. This means there must exist at least one node which breaks the BST assumption; let's call this node $v$.

Now, there are two ways $v$ could break the BST assumption. One way is if there's a node in $v$'s left subtree with label greater than $v$. The other way is if there's a node in $v$'s right subtree with label less than $v$.

But everything in $v$'s left subtree must come before it in the in-order traversal, and everything in its right subtree must come after it. And we assumed that the in-order traversal is sorted.

Thus, there's a contradiction, and such a tree cannot exist.

(*EDIT:* As RemcoGerlich points out, this is only true if your tree is known to be binary. But if it's not binary, an in-order traversal isn't defined, afaik.)

# Answer
> -1 votes
Yes, another way is to think about the In-order Traversal. You go Left-Root-Right. Well a property of BST is the left node is less than Root and right node is greater than Root. By going in the specified order, you start with the left most sub tree, and work your way over to the right most subtree. This will result in sorted order, else this would be Tree structure, not a Binary Tree Structure.

# Answer
> -2 votes
It is true only if there are no duplicates.

---
Tags: algorithms, data-structures, binary-search-trees
---


# Question
Title: Sample a set of N numbers without replacement, each element taken from N different weighted sets
Here's my problem: I have $N$ sets of integers $S\_i$ where $|S\_i| = n\_i \forall i \in \[1,N\]$ each with non-uniform weights $W\_i = \\{w\_{i,1}, ..., w\_{i,n\_i}\\}$ such that $\sum\_{j}{w\_{i,j}} = 1$. I want to sample $m$ unique **lists** $P\_{k \in \[1,m\]} = (p\_{k,1}, ...,p\_{k,i}, ...,p\_{k,N})$ of $N$ integers (including duplicates, and ordering matters), with each element $p\_{k,i} \in S\_i$.

The naive implementation I use as a proof of concept to generate a new unique list $P\_k$: I pick an element from $S\_1$ at random according to the weights $W\_1$, then I pick an element from $S\_2$ with weights $W\_2$, etc... until I have $N$ elements to create a candidate list. If this list is not unique among exiting lists, I discard it and start again at the top, otherwise it becomes the list $P\_k$. This is repeated until I get $m$ unique lists.

Although it works and gives me the correct result, this is very inefficient as I get more and more duplicate sets as $m$ increases, and as the weights $w\_i$ diverge from a uniform distribution.

Here's an example with disjoint sets: $N=3, n\_1=4, n\_2=3, n\_3=5$ $$ S\_1 = \\{1, 2, 3, 4\\}; S\_2 = \\{11, 12, 13\\}; S\_3 = \\{21, 22, 23, 24, 25\\}; $$ With $m=3$, a possible sampling would be: $$ P\_1=(1, 11, 21), P\_2=(1, 12, 24), P\_3=(3, 12, 22) $$

All the sampling algorithms I have found either assume uniform distribution, or require "flattening" my problem from $N$ sets to one set of all possible combinations (and calculating the corresponding weights). Although the computation of the weight for a specific combination is trivial, it is not feasible for the size and number of sets I'm working with: $2 \leq N \leq 20$ and $2 \leq n\_i \leq 50$. Typically $1 \leq m \leq 1000$ and $m \leq \prod\_{i \in \[1,N\]}{n\_i}$.

Does anyone has an idea to replace my current naive solution? I am looking for an algorithm that would allow me to make that sampling without replacement **a.** directly from $S\_i$ and $W\_i$, or **b.** a 1D weighted sampling algorithm that does not require pre-computing all possible combinations and corresponding weights.

# Answer
There is a mapping from each possible list $P$ to an interval $\[\ell,r)$ contained in $\[0,1)$, such that the resulting intervals (if you consider all possible lists) form a partition of $\[0,1)$.

In particular, if $P=(p\_1,\dots,p\_N)$ and $N\ge 1$, define

$$f(P) = w\_{p\_N} f(p\_1,\dots,p\_{N-1}) + w\_1 + w\_2 + \dots + w\_{p\_N-1};$$

and if $N=0$, define $f(p\_1) = \[0,1)$. Also, given $x \in \[0,1)$, you can find $P$ such that $x \in f(P)$ in a straightforward way.

Now one way to sample from your distribution is to sample a real number $x\_1$ uniformly at random from $\[0,1)$, then map it back to the corresponding list $P\_1$, i.e., find $P\_1$ such that $x\_1 \in f(P\_1)$, and output $P$.

If you want to sample a second list $P\_2$ that is guaranteed to be different from $P\_1$, sample $x\_2$ uniformly at random from $\[0,1) \setminus f(P\_1)$, find $P\_2$ such that $x\_2 \in f(P\_2)$, and output $P\_2$.

To sample a third list $P\_3$ that is different from $P\_1,P\_2$, sample $x\_3$ uniformly at random from $\[0,1) \setminus (f(P\_1) \cup f(P\_2))$, find $P\_3$ such that $x\_3 \in f(P\_3)$, and output $P\_3$.

Repeat. Note that $\[0,1) \setminus (f(P\_1) \cup \cdots \cup f(P\_m))$ can be expressed as a disjoint union of $m+1$ intervals, and you can sample uniformly from it in $O(m)$ time, so the running time to generate $m$ different $P$'s is something like $O(m^2N)$. This should be good enough to accommodate your parameter settings. (In fact, by storing that union of intervals in a self-balancing binary tree structure, you can sample in $O(\log m)$ time, so you can reduce the total running time to $O(mN\log m)$, but that probably won't be necessary for your parameter settings.)
> 1 votes

---
Tags: algorithms, combinatorics, probability-theory, sampling
---


# Question
Title: Is there a maximal order of computable functions?
Busy Beaver is an uncomputable function that grows quicker than any computable function. That means there exist functions f such that for all computable functions g: g in O(f). There is an upper bound on the order of computable functions.

The question is whether or not there is a **computable** function like that. So, is the set of orders of computable functions closed or open?

And if yes, do we know examples of such functions?

# Answer
Suppose that such a computable function $f$ exists. The function $h(n) = nf(n) + n$ is also computable, but $h(n)$ is not $O(f(n))$.

We can similarly rule out a uniformly computable countable order, that is, a uniformly computable sequence of functions $f\_i$ such that for each computable $g$, we have $g = O(f\_i)$ for some $i$. Indeed, given such a sequence, the function $h(n) = n\max(f\_1(n),\ldots,f\_n(n))+n$ is computable and is not $O(f\_i)$ for any $i$.

In contrast, if we remove uniform computability, then it is trivially possible to find such a sequence, namely take an enumeration of all computable functions. Taking $F\_i = \max(f\_1,\ldots,f\_i)$, this even gives a computable scale of functions $F\_1 \leq F\_2 \leq \cdots$.
> 0 votes

---
Tags: complexity-theory
---