title: Why are mathematical proofs so hard?

text:
# Question
Title: Why are mathematical proofs so hard?
I am an electrical engineer and trying to make a transition into machine learning. I read in multiple articles that I have to learn data structures and algorithms, before this I have to learn about mathematical proofs. I started studying it on my own using the material available on MIT's OCW, while I did grasp the concepts of induction and well ordering etc..

I've been struggling with the exercises for a very long time and it's really frustrating. I can easily deal with any type of proofs that I saw before (e.g. once I saw the proof of a recurrence question I became pretty good at proving them). My problems start when I face an unusual question. I feel like I am memorizing the proofs rather than learn how to prove.

Is there any way (or any resources) that can improve my proving skills in a way that whenever I see an unusual question (like the checkers tiles and chess tiles type of questions) I don't have to stare at them for 2 hours before giving up?

# Answer
> I feel like i am memorizing the proofs rather than learn how to prove

You *can't* learn "how to prove". "Proving" is not a mechanical process, but rather a creative one where you have to *invent* a new technique to solve a given problem. A professional mathematician could spend their entire life attempting to prove a given statement and never succeed.

> I can easily deal with any type of proofs that i saw before ( eg. once i saw the proof of a recurrence question i became pretty good at prooving them). My problems start when i face an unusual question.

That is normal. Any mathematics "proofs" course isn't designed to teach you how to take an arbitrary problem you've never seen before and be able to solve it (since nobody, not even the best mathematics professors can do that). Rather, your learning goals are

1. Learn how to "read" proofs and judge their correctness
2. Learn how to "write" down a proof in the right mathematical language
3. Learn about known proof "techniques" and how to apply them

If you are working on a new, unknown problem, it is normal that you might not be able to solve it. However, *knowing* and having memorized other proof techniques may help you. Often proofs involve combining a new idea with existing known proof techniques. The more, and the more varied the proofs you already know are, the better your chance of being able to solve the given problem.

You are on the right track. You should simply keep studying proof techniques. The exercises you are doing are good. Don't worry if you get stuck. As you get more experienced and your "toolbox" of techniques grows, you will be able to solve exercises that are less "alike" the previous ones you have seen.
> 42 votes

# Answer
As other authors have mentioned, partly because proofs are inherently hard, but also partly because of the cold fact that ***proofs are not written for the purpose of teaching***, even in most textbooks. Rather, most proofs are written out of a kind of obligation, as a sort of run-away argument; not presenting proofs at all is considered unacceptable, but writing them in exhausting details would burn the author out as well as endanger the reader getting lost in the woods. Hence, most proofs are succinct on purpose, leaving a lot of dots solely for the reader to connect themselves. While some people find this a helpful exercise, many readers like you and me find it making mathematics unnecessarily challenging. This is also why classroom pedagogy in a university setting is indispensable for professional mathematic learning as the tools of dialogue can fill in the blank of textbook proofs.
> 12 votes

# Answer
I can certainly recommend the book of G. Polya's, *How to Solve It*. It is a standard classic, not to be missed. There is a newer book *How to Read and Do Proofs: An Introduction to Mathematical Thought Processes* by Daniel Solow that may be more accessible.

In any event doing proofs is entirely *Unnatural* for humans. It is a discipline that requires careful thought we do not normally use. We are used to making many assumptions to get through our days and our lives. If we had to justify the first of them we could not get out of bed. A mathematical proof strips away the assumptions and lives on only what you can show clearly and unambiguously.

I had the similar trouble with problems over trigonometric identities. Trying to get from the start to the finish is easy when there is a known, learned method. Identities may require multiple steps in unknown directions without much sense of direction. Proofs are a bit easier since the *logical* methods are fairly limited and known (if you read the books). Keep at it.
> 11 votes

# Answer
I like Tom's answer: there's no magic bullet but you just need to continue doing exercises and gradually you will develop a better intuition and know how to attack a problem.

As for resources, you might like G. Polya's book How to Solve It. Looks like the Wikipedia article gives a nice and somewhat detailed overview. Basically, the book will offer you a strategy or methods for dealing with mathematical statements and their proofs.
> 4 votes

# Answer
> Why are mathematical proofs so hard?... I have to learn data structures and algorithms,

My guess is you'll also want to learn about algorithms' space and time complexity, as quantified in big O notation. Time complexity, in particular, hints at why proofs are hard. If I promised you there is a proof of at most length $n$ of a given statement, how would you find it? In theory, you could go through all proofs of length $\le n$ until you find one, which would take exponential time, say $O(ne^{cn})$ (I've included a factor of $n$ for reading time). That's far too inefficient for our purposes, unless $n$ is very small. There might be a much better algorithm, but no-one's found a particularly efficient general one. That's why proving things remains a "creative" exercise, by which we mean "we don't know in pseudocode terms how such thinking works".

> Is there any way (or any resources) that can improve my proving skills in a way that whenever I see an unusual question (like the checkers tiles and chess tiles type of questions) I don't have to stare at them for 2 hours before giving up?

You call such questions unusual, yet you know what examples to give. That's the crux of the issue right there. It's only "unusual" in your experience if you've not seen it (much). As other answers note, just keep learning more tools. Hopefully, you should then be able to tell which ones help with a problem. Judging by your choice of examples, the use of invariants in proofs is something you could work on. I don't know how good your big/small O notation is, but I'll mention that topic again because it's often useful to prove results, such as inequalities or anything dependent on them, e.g. limits (at least if you're meant to give an $\varepsilon$-$\delta$ proof).
> 4 votes

# Answer
Some proofs have to be cumbersome, others just are cumbersome even when they could be easier but the author didn't came up with a more elegant way to write it down. Coming up with a simple proof is even harder than understanding a proof and so are many proofs more complicated than they should be.

There is no general advice how to understand proofs (elegant or not). Some technique that you can try is to disprove the statement. Why does the proof work? What would happen when you leave out one of the preconditions for the proof?
> 3 votes

# Answer
If you're already pretty handy with programming, you might enjoy learning to use an interactive proof assistant like Coq or Lean. A proof assistant is a programming language with a very rich type system in which it's possible to express constructive logic. These kinds of languages largely operate on the notion that there's a direct analogy between programs and their types on the programming side, and between propositions and proofs on the math side. (This is called the Curry-Howard isomorphism.)

A really interesting project on these lines is the Natural Number Game. The game is part of a larger program by several professors at Imperial College of London to formalize all of undergraduate mathematics using the proof assistant Lean. At the start of the game, you're given just the Peano axioms of arithmetic: 0 is a natural number, the successor of a natural number is a natural number, and the successor of any natural number is not equal to itself. You're allowed to use the usual rules of predicate logic and induction. The object of the game is to come up with rigorous, formal proofs of the properties of addition, multiplication, and some basic number theory.

Proof assistants effectively gamify doing pure mathematics -- they remember the rules for you and they give you feedback practically in real time. If you're looking for a way to improve your skills at doing proofs through self-study, I think proof assistants are great tools. On top of that, they're also used in formal verification of computer programs, which is an interesting and employable specialization in its own right.
> 3 votes

# Answer
> I've been struggling with the exercises for a very long time and it's really frustrating. I can easily deal with any type of proofs that I saw before (e.g. once I saw the proof of a recurrence question I became pretty good at proving them). My problems start when I face an unusual question. I feel like I am memorizing the proofs rather than learn how to prove.

So you do know how to read proofs, but you're finding these ones to be difficult. I think there are probably a few things that are relevant.

One is that differences between ability required by different mathematical textbooks is exponential, not linear. I have seen books titled "Introduction to X" that are much harder than books titled "Advanced Y". Authors have in mind different audiences, and the levels of difficulty are correspondingly different.

Second, it might just be that once you get more familiar with concepts and proofs in a particular area, they will become easier. As some of the other answers indicate, proofs often leave out steps that the author thinks would be obvious for their intended audience. None of us would expect a proof to point out that two plus two equals four. Some things that one reader finds completely mysterious are like $2+2=4$ for other readers. That doesn't mean that the book or article isn't for you, though. If you can work through the missing steps, you will get a deeper understanding of the subject, and after you do that a few times, what was difficult will become easier. (A proof in a book that's a little bit too hard is like an exercise.)

Third, I understand if you don't want to stare at a proof for two hours, but I think that during that period, you may be learning a lot. What you are doing during that time is thinking through different interpretations of the concepts and steps and possible ways to get from one step to another, and thinking about what assumptions the author had in mind. That is a learning process, and I think that doing that helps one understand other things more easily, later.

I do a lot of self-study in subjects that are unfamiliar to me. Sometimes I use two or three books for one subject, because what's left out in one book will be explained more clearly in the other. Sometimes I find that I have to go and read books on other subjects, because the author assumed that their readers would all have a certain background--and I don't have it. That doesn't necessarily mean I read the entire book on the other subject. Sometimes I just read enough so that I can understand the book I really want to understand. This is not a bad practice. I end up learning things that I wasn't interested in learning, but that turn out to be useful later.

(Maybe all of this seems obvious, but hopefully some comment here is helpful to someone.)
> 3 votes

# Answer
I am an electrical engineer as well as a mathematician by training. After completing my undergraduate in EE, I switched to maths and finally obtained a hard-earned doctorate in it. I won't say that I am a particularly bright kid. However I have always found mathematics easy and consequently boring. However, thanks to my dad, even at a very early age (about eight or nine) I knew that there is far more to maths than my school. So I endured it.

I also derived my self-esteem from being good at maths (yes, wrecks like me do exist). I probably still do.

Since I progressively did less and less maths, by the time I completed my high school, I was somewhat scared of it. My situation would be very much that same as yours in my first or second year of undergraduate, which was very bad for my self esteem. Then I begun my reeducation in maths - largely by self-study and also by way of audit courses, which I attended at the expense of my regular EE curriculum. EE, anyway, was a cake-walk for me. But mathematics proved a very hard nut to crack.

I continued my mathematics studies after college, enrolled into maths program and after a long, hard and frustrating struggle did complete my doctorate.

I don't know which area of maths you are looking at. But I will not suggest any online resources or guest lectures to get entry into maths. Such things only give you an illusion of understanding. You will *have* to pick up a book. You will *have* to pick up a pen. And you will *have* to start writing. And you too will learn the hard way, *only* the hard way. If you have someone to discuss things with, great! Else toil in obscurity.

To begin with, talk to someone to get the first couple of books suitable for you. Rest you can figure out yourself.
> 2 votes

# Answer
I can't believe no one else is mentioning this but you are probably overdoing it if you want to learn applied machine learning. You'd be better off brushing up on linear algebra, and basic computer science. There are some great specializations on coursera - specifically the Machine Learning and Mathematics for Machine Learning tracks (it says there is a cost but you can audit each of the courses individually for free - there are about 8 of them total between the two specializations); Andrew Ng's Deep Learning specialization (5 courses) is also fantastic. Then sign up for Kaggle and apply what you're learning. I understand personally wanting to know how to derive mathematical proofs with rigor but no one is paying you to do that in production. You're better off actually studying machine learning.
> 2 votes

# Answer
It sounds like your issue is that you lack experience with logical reasoning in general. The fact that you can prove similar theorems easily by adapting a proof that you have seen before, shows that you do not have a problem with understanding proofs. But I suspect you have never learnt first-order logic proper, which is a necessary ingredient in real mathematical reasoning. Once you learn a deductive system for FOL (for which I recommend Fitch-style), it actually becomes easy to deal with arbitrary areas of mathematics even if they are completely new. However, there is an upfront cost, which is roughly half the effort you need to put in to learn a new programming language. So I leave you to decide whether to try or not.

Independent of learning FOL, you also need a source for practice, and for that I recommend How to Prove It by Daniel Velleman. It does teach you a bit of logical reasoning, and it gives you plenty of neat and interesting things to prove.
> 0 votes

# Answer
Theoretically Proof Search is a rather high-complexity computational task.

For the case of Boolean propositions, it is coNP-complete, and therefore conjectured to not have algorithms that are faster than exponential in the size of the formula you want to prove.

For proof in Peano Arithmetic (and many stronger systems like standard set theory ZFC), it is undecidable. So there is no "algorithm" that one can learn and follow to find proofs.

Godel, in his famous letter to von Neumann, speculates about the possibility of an efficient algorithm that can be used to find proofs. Turns out he was kind of touching on the subject of P vs. NP.
> 0 votes

---
Tags: proof-techniques, induction
---


# Question
Title: Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph
So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general case, it is exponential.

I am trying to determine whether the number of maximal cliques in a $(2C\_4, C\_5,P\_5)$-free graph is linear or polynomial with respect to the number of vertices.

In a $(2C\_4, C\_5,P\_5)$-free graph, the largest induced cycle is of length 4, and no two 4-cycles are edge-disjoint.

Is there a paper that mentions such result?

# Answer
(Answered also on https://cstheory.stackexchange.com/questions/47691/)

A ($2C\_4$, $C\_5$, $P\_5$)-free graph may have exponentially many maximal cliques. For example, the complement of the disjoint union of $n/3$ triangles with $3^{n/3}$ maximal cliques is $K\_1 \cup K\_2$-free, and thus has none of $2C\_4$, $C\_5$, $P\_5$ appear as an induced subgraph. https://doi.org/10.1007/BF02760024

Note: If the complement of a graph has $k$ pairwise independent edges, then they give you $2^k$ maximal cliques. Conversely, it is known that the number of maximal cliques is upper-bounded by a function of the maximum number of independent edges in the complement . https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230230308
> 3 votes

---
Tags: graphs, reference-request, clique
---


title: Term-rewriting software recommendation

text:
# Question
Title: Term-rewriting software recommendation
Is there an easy to use software that implements term-rewriting? Or do I need to write my own parser for it?

I am looking for something that will take in a fixed set of user-specified rules and will be able to reduce arbitrary terms under those rules. Is there a standard tool for doing such rewrites?

# Answer
PLT Redex has support for term rewriting. You'll find that most of the examples are focused on small-step operational semantics for programming languages, but in general the system allows for arbitrary rewriting, including non-determinism. It also has a bunch of nice features, like randomized testing of properties, alpha-equivalence, steppers for visualising/debugging, and excellent graphical output.

If you want higher-order syntax, you might be interested in something like ELPI.

For a super-lightweight prolog-style programming, you might be interested in miniKanren.
> 2 votes

# Answer
The computer language Prolog has a term parser built in, and you can represent re-write rules in Prolog clauses, see

https://www.youtube.com/watch?v=b2Px7cu2a68
> 0 votes

---
Tags: term-rewriting
---


# Question
Title: $g ( n ) ∈ ω ( 1 )$ and $f ( n ) ∈ o ( g ( n ) )$ imply $2 f ( n ) ∈ o ( 2 g ( n ) )$
> Prove that if $g ( n ) ∈ ω ( 1 )$ and $f ( n ) ∈ o ( g ( n ) )$, then $2 f ( n ) ∈ o ( 2 g ( n ) )$.

I was going over this question in my Algorithms class and could'nt understand why first condition has to be met. How would $g ( n ) ∈ ω ( 1 )$ affect our reasoning? Also, what would happen if instead of $g ( n ) ∈ ω ( 1 )$, it was $g ( n ) ∈ o ( 1 )$?

# Answer
Considering non negative case we have $$O(f)=\\{g: \exists C\>0, \exists N \in \mathbb{N}, \forall n\>N, g(n) \leqslant Cf(n)\\}$$ From this definition for $\forall C\>0,$ we have: $$ C \cdot O(f)= O(C \cdot f) = O(f)$$ It can be written also as: $$C \cdot g \in O(f) \Leftrightarrow g \in O(C \cdot f) \Leftrightarrow g \in O(f)$$ without any additional condition.
> 1 votes

---
Tags: big-o-notation
---


# Question
Title: How to estimate the computational cost in a neural network?
Given a neural network(assuming no regularisation/dropout), I want to determine the computational cost of doing a forward and a backward pass of a datapoint. I want the measure to be of independent of the programming language/operating system involved. I can think of it as a graph model, with some activations applied on nodes, then I think it can be estimated by hand. Also is there any online tool/package which would do the estimate if I input the neural network ? I am new to computer science, so probably it is a very naive question to most of the users, I am offering my apologies it is so.

# Answer
It takes $O(n)$ time, where $n$ is the size of the neural network (e.g., number of nodes plus number of connections; in a graph model, number of vertices plus number of edges).
> 1 votes

---
Tags: graphs, neural-networks
---


# Question
Title: Linear programming vs integer linear programming
Given $A,b$, let $Ax \le b$ be an instance of linear programming on the variables $x=(x\_1,\dots,x\_n)$. Assume that the constraints $0 \le x\_i$ and $x\_i \le 1$ are included in $A,b$.

Suppose that there is a feasible solution $x \in \mathbb{R}^n$ to the linear programming problem where $x\_1 = 1$. Also, suppose there exists a solution to the corresponding integer linear program, i.e., there exists $x' \in \\{0,1\\}^n$ such that $Ax' \le b$. Are we guaranteed that there exists a solution with $x'\_1=1$, i.e., there exists $x' \in \\{0,1\\}^n$ such that $Ax' \le b$ and $x'\_1=1$?

To put it another way: if we solve the linear program associated with a zero-or-one ILP instance, and find that one of the variables gets assigned to 1 in some solution to the linear program, does it follow that there exists a solution to the ILP instance where we set that variable to 1?

I am skeptical but could not find either a proof or a counterexample.

# Answer
> 2 votes
The program $x\_1 + 2x\_2 = 2$ has the integer solution $(0,1)$ and the fractional solution $(1,1/2)$ but not an integer solution of the form $(1,\cdot)$.

# Answer
> 0 votes
Yuval Filmus suggests a counterexample: $x\_1 + 2x\_2 = 2$, $0 \le x\_1 \le 1$, $0 \le x\_2 \le 1$.

Here there is a feasible solution to the LP instance with $x\_1=1$, namely, $x\_1=1$, $x\_2=1/2$.

However the only feasible solution to the ILP instance is $x\_1=0$, $x\_2=1$.

---
Tags: linear-programming, integer-programming
---


# Question
Title: Is there such thing as "sequential types"?
I am wondering how you could possibly define the *implementation* of an imperative function as a type. Is it possible? Currently I only see the input parameters and output result used in the definition of a function type, but how could you also include the implementation in the type definition?

# Answer
> 6 votes
The seminal paper on this topic is *Linear Types Can Change the World!* by Phil Wadler.

Of course, with a title like that, you know it has to be a Wadler paper. It's a pun, the implication being that linear/uniqueness type system allows you to represent operations which mutate the world state.

You can use linear types today in languages such as Clean. See, for example, Aachen et al, *High Level Specification of I/O in Functional Languages*.

In logic languages, you can do the same thing with strong *modes* rather than strong types, such as in Mercury. (Full disclosure: I'm one of the original Mercury developers.) See Fergus Henderson's honours thesis, *Strong Modes can Change the World!*

**EDIT**

I think I may have misinterpreted the question, which I thought was about types for imperative code.

The answer to your question is "yes, absolutely". There is a tradeoff between types and programs. At one end of the spectrum, you have a completely dynamic type system, where every program has the same type. At the other end, you have a hyper-static type system, where every type only has one program that is of that type, with the type essentially encoding the program.

In the middle ground, there are many programming languages whose type systems are Turing-complete, including Haskell, Java, TypeScript, and Rust.

# Answer
> 3 votes
I'll admit I'm confused about the details of your question: you want the *implementation* of a program to appear in its *type*? Usually types talk about *behavior*. That's why they're useful!

The idea of having the *full* specification of a procedure appear in types is very suggestive of dependent type theory. Traditionally these theories only apply to languages without mutability, which might be the point of your question.

But computer scientists have been working diligently to integrate well-known methods of analyzing imperative languages into theories of dependent types. One example is Hoare Type theory, see e.g. the paper Hoare Type Theory,Polymorphism and Separation.

# Answer
> 3 votes
Yes. Before I give the answer, let me set the stage.

### Giving types to expressions and functions

Historically, programming languages started to have types to qualify *memory locations*: does the memory cell where `x` is stored contain an integer or a floating-point value? Type enforcement is then to check (or coerce) that the *value* that gets stored into `x` has the correct type. `x := <expr>` is well-typed if the value of the expression `expr` has the same type as `x`. This generalizes typing from values to *expressions*: the type of an expression is the type of its value.¹

So we'll consider type systems that assign types to expressions. A statement that the expression $M$ has the type $T$ is written $\Gamma \vdash M : T$, where $\Gamma$ is an *environment* (also called *context*) that lists the types of the variables that are present in $M$.

When reasoning about expressions and their values, it's often useful to consider not only the expression and the value, but the evaluation rules that lead from one to the other. The most common way to describe the evaluation rules of a program is through reduction rules that define how an expression can be reduced (simplified) to another. A value is an expression that cannot be reduced any further. A reduction rule has the form $$ M \longrightarrow M' $$ stating that $M$ can be reduced in one step to $M'$.

If you define both reduction rules and a type system for a language, they had better be compatible. The property that defines their compatibility is *type preservation* (also called *subject reduction*): if an expression has a certain type, then what it reduces to still has that type. In mathematical notation: if $\vdash M : T$ and $M \longrightarrow M'$ then $\vdash M' : T$.

Let's see what type preservation can tell us about the types of functions. The rule to reduce a function application is beta reduction: $$ \underbrace{(\lambda x. M)}\_{?} \\, \underbrace{\strut N}\_{U} \longrightarrow \underbrace{M\[x \leftarrow N\]}\_{T} $$ For type preservation, if the right-hand side has the type $T$, we want the left-hand side to have the type $T$ as well. Given an argument of type $U$, we want $\lambda x.M$ to have a type that ensures that $M$ will have the type $T$ once we replace $U$ with a value of type $U$. To keep things simple, let's stick to functions that require their argument to have a specific type: assuming that $x$ has the type $U$, $M$ must have the type $T$. The type of $\lambda x. M$ is the type of functions that map values of type $U$ to values of type $T$, which we'll write $U \rightarrow T$. And the function $\lambda x.M$ has the type $U \rightarrow T$ if $M$ has the type $T$ under the assumption that $x$ has the type $U$: $$ \dfrac{x : U \vdash M : T}{\vdash (\lambda x. M) : U \rightarrow T} $$

(Note that I'm not saying that this is the only way to define a type system for functions and function application. I'm just showing one way to make it work, without covering all the details. What I'm showing is the simply typed lambda calculus.)

### Effect types

So far we've seen how to type expressions and functions if the only thing that interests us about the type of an expression is the type of the value that it reduces to. Now let's extend that to encode other information about an expression in its type.

If the semantics of an expression is more than its value, we'd better encode that in the runtime semantics. So let's add ***labels*** to the reductions. Labels encode information about the behavior of the expression. The most common use of labels is to encode side effects. For example, let's consider a language with a `print` function that doesn't return anything. The “expression-value type” of `print` is $\mathsf{char} \rightarrow \mathsf{unit}$ (it returns a value of the unit type, which carries no information). The expressions `print('a')` and `print('b')` both evaluate to the unit value `()`, which is pretty boring. What's interesting is what they print, so let's annotate the reduction relation with what gets printed. $$ \mathtt{print}(c) \xrightarrow{c} () $$ The sequence of labels in a sequence of reductions is called a ***trace***. For example $$ \mathtt{print}(\mathtt{'a'}); \mathtt{print}(\mathtt{'b'}) \xrightarrow{\mathtt{'a'}} \mathtt{print}(\mathtt{'b'}) \xrightarrow{\mathtt{'b'}} () $$ is a sequence of two reductions with the trace $(\mathtt{'a'}, \mathtt{'b'})$. In this toy example, the trace of the reductions of an expression is what it prints. More generally, the trace of the reductions of an expression describes its runtime behavior.

If we want to capture the runtime behavior of an expression in its type, we need to convey the trace in the typing. The usual way to do it is to add an ***effect*** annotation to typing statement: $\Gamma \vdash M :\_e T$ states that given the types of the variables in the environment $\Gamma$, the expression $M$ has the type $T$ and the effect $e$. (Notations can vary.) The name “effect system” comes from the fact that the most common use is to track side effects of expressions. In its most basic form, $e$ would be the trace of $M$, but the point of a type system is usually not to know *all* the details, just relevant details. So just like we usually work on types like `int` and `char` which are sets of values (or at least which stand for sets of values), the effect annotation $e$ is a set of traces, or more generally it represents a set of traces. For example, the effect of $\mathtt{print}(c)$ is $\\{c\\}$, because the only possible trace of this expression is the one-character string $c$. In mathematical notation: $\vdash \mathtt{print}(c) :\_{\\{c\\}} \mathsf{unit}$.

What does this mean for functions? As before, we want the type of a function to contain enough information to determine the type of its result. For this example, let's stick to call by value: the argument $N$ is a value, and evaluating it has an empty trace (by definition of a value, the sequence of reductions from it is empty). Reducing the function application has no side effect: any side effect from the evaluation will come from further reductions of the body. $$ \underbrace{(\lambda x. M)}\_{?} \\, \underbrace{\strut N}\_{U} \longrightarrow \underbrace{M\[x \leftarrow N\]}\_{\xrightarrow{e} T} $$ In order for the right-hand side to be well-typed, we want the fact that the left-hand side is well-typed to guarantee that $x : U \vdash M :\_{e} T$. So the type of $(\lambda x. M)$ should guarantee that its effect is $e$, in addition to guaranteeing that its result has the type $T$: $$ \dfrac{x : U \vdash M :\_{e} T}{\vdash (\lambda x. M) : U \rightarrow\_{e} T} $$ We've annotated function types with effects: $U \rightarrow\_{e} T$ is the type of functions that take an argument of type $U$ and return an argument of type $T$ after having the effect $e$.

Here's a sketch of the definition of a different, extremely simple effect system that just indicates whether an expression is *pure* (no side effect) or *impure* (might have side effects). The grammar of effects is just $e ::= \mathsf{P} \mid \mathsf{E}$. We define the combination of two effects as $e\_1 \sqcup e\_2 = \mathsf{P}$ if $e\_1 = e\_2 = \mathsf{P}$ and $e\_1 \sqcup e\_2 = \mathsf{E}$ otherwise: the combination is pure only if all the parts are pure. The typing rules for lambda abstraction and for function application are $$ \dfrac{\Gamma, x:U \vdash M :\_{e} T} {\Gamma \vdash (\lambda x.M) :\_{\mathsf{P}} U \rightarrow\_{e} T \\} \qquad \dfrac{\Gamma \vdash M\_1 :\_{e\_1} U \to T \qquad \Gamma \vdash M\_2 :\_{e\_2} T} {\Gamma \vdash M\_1 \\, M\_2 :\_{e\_1 \sqcup e\_2} T} $$ A lambda abstraction is always pure: the effects of the function are only unleashed when the function is applied to an argument.

Effect systems can be very simple or very complex, depending on what aspects of the runtime behavior you want to model and how precise the model you want to be. They're a very general framework for reasoning about the behavior of programs. Here are a few examples of behaviors you can model with an effect system:

* The exceptions that an expression might raise (as Java does).
* The I/O that an expression might perform.
* The channels over which a process might communicate (this is usually what's of interest when typing process calculi).
* Whether an expression might not terminate (it's sometimes advantageous to treat non-termination as a side effect).
* How long it takes to evaluate an expression (for real-time systems).

### Singleton types

You asked how to “define the implementation of an imperative function as a type”. Effect systems let us capture aspects of the behavior of the function. But effect systems usually don't capture all the aspects of the behavior, because that would be too unwieldy. If you need to express “exactly this function, and not just something with similar behavior”, type theory has a concept for that: ***singleton types***.

A singleton type is a type that contains a single value. The expression $M$ has the singleton type $\mathsf{S}(V)$ if and only if the value of $M$ is $V$. (More generally, with non-termination, $M$ might have the type $\mathsf{S}(V)$ if its only *possible* value is $V$; if $M$ doesn't terminate, it has the type $\mathsf{S}(V)$ for every $V$.)

With functions, it's usually impossible for a compiler to decide whether two implementations of a function are identical, so in order for a function to have a singleton type $\mathsf{S}(\mathtt{foo})$, the compiler has to be able to track that the specific function $\mathtt{foo}$ was passed around. With data types, a compiler might have a chance of allowing $2+2$ to have the type $\mathsf{S}(4)$.

Singleton types aren't very interesting on their own, but they become interesting when combined with other language features. Here are a few examples of uses of singleton types.

* If you can take the union of singleton types, you can express that the value of an expression is in a finite set, for example to constrain the range of an integer expression.
* The Ocaml module system has a form of singleton types for modules.
* In Haskell, singleton types are often used used to sneak dependent types into the language.
* Rust has singleton types for functions, called function item types.

¹ <sub> There are many common generalizations, such as subtyping, polymorphism, coercions, etc. but I won't go into them unless they're relevant to the question at hand. So if you're reading this and thinking “this isn't the whole story”, yes, this isn't the whole story. I'm writing an answer, not a treatise. </sub>

# Answer
> 1 votes
You could use the *singleton types*, see the paper Extensional equivalence and singleton types by Robert Harper and Christopher Stone and Chapter 9 of Advanced Topics in Types and Programming Languages.

Briefly, the idea is to extend the type system with *singleton types* $\\{A \mid t\\}$ which intuitively means "the type of values of type $A$ that are equal to $t$". For example, $\\{\mathtt{nat} \mid 2 + 3\\}$ is the type of natural numbers equal to $2 + 3$.

The singleton types are used in modules to express sharing constraints.

---
Tags: type-theory
---


# Question
Title: How to prove that knapsack has no competitive algorithm
In online knapsack problem, items arrive one by one. Each time an item $i$ arrives, its weight $w\_i$ is revealed. We would like to maximize, in an online fashion, the number of items placed in a bin of capacity $W$.

The proposition that I am trying to prove is that no deterministic competitive algorithm exists for this problem.

I did something like this: assume that an online algorithm decided to place an item $j$. Then the adversary can choose a sequence of items in a way that the online algorithm places only a single item. In other words, it chooses the sequence where $w\_j=W$ and all other items have $w\_i$ small enough to make the competitive ratio grows without bound.

This proof seems wrong because I did not fix the sequence of input beforehand, right? (My input sequence changes when the online algorithm changes.) I should fix the input, then prove that no online algorithm is competitive. How to do this?

# Answer
Let's check the *definition* of a competitive algorithm, in your specific case. For simplicity, we assume that $W = 1$.

We can describe an algorithm for Knapsack as a sequence of functions $A\_n\colon \mathbb{R}\_+^n \to \\{0,1\\}^n$, describing which items are taken given their weights, which satisfies the following two properties:

1. The result fits inside the knapsack: for all $w \in \mathbb{R}\_+^n$, if $x = A\_n(w)$ then $\sum\_{i=1}^n x\_i w\_i \leq 1$.
2. The algorithm is online: for all $w \in \mathbb{R}\_+^n$ and $m \leq n$, if $x = A\_n(w)$ and $y = A\_m(w\_1,\ldots,w\_m)$ then $x\_i = y\_i$ for $i = 1,\ldots,m$.

The algorithm is furthermore $c$-competitive if:

3. For all $w \in \mathbb{R}\_+^n$ and $o \in \\{0,1\\}^n$ such that $\sum\_{i=1}^n o\_i w\_i \leq 1$, if $x = A\_n(w)$ then $\sum\_{i=1}^n x\_i \geq c \sum\_{i=1}^n o\_i$.

(Your definition might put $c$ on the other side of the inequality.)

---

Suppose now that $A$ is a $c$-competitive algorithm, where $c \> 0$, and let $N = \lceil 1/c \rceil + 1$, so that $cN \> 1$.

Consider $w\_1 = 1$ and $o\_1 = 1$, which satisfies $o\_1 w\_1 = 1$. By Property 3, $x\_1 = A\_1(w\_1)$ satisfies $x\_1 \geq co\_1 = c \> 0$, and so necessarily $x\_1 = 1$.

Now consider $w = 1,1/N,\ldots,1/N$, where there are $N$ many $1/N$'s, and $o = 0,1\ldots,1$, where there are $N$ many $1$'s. These vectors satisfy $\sum\_{i=1}^{N+1} o\_i w\_i = 1$. Let $x = A\_{N+1}(w)$. By Property 2, $x\_1 = A\_1(w\_1) = 1$. By Property 1, $x\_2 = \cdots = x\_{N+1} = 0$. By Property 3, $$1 = \sum\_{i=1}^{N+1} x\_i \geq c\sum\_{i=1}^{N+1} o\_i = cN, $$ which contradicts the choice of $N$. This contradiction shows that no $c$-competitive algorithm exists.

---

Here is how this proof would usually be presented. Consider any competitive algorithm. We start by presenting it an item of weight $1$. If the algorithm doesn't take the item, then we immediately end the stream, and so the algorithm is revealed to be $0$-competitive (comparing to the solution which does take the item). Otherwise, we present it $N$ more elements of weight $1/N$. The algorithm's knapsack is already full, so it cannot take them. Since instead it could have taken only the $N$ low-weight elements, this shows that the algorithm isn't even $1/N$ competitive. Since $1/N$ can be arbitrary small, we reach a contradiction.

Notice how this argument is much less formal and much more "intuitive", if not particularly shorter (though this is only an artifact of this particular argument being so simple). We usually present it in the latter form, keeping in mind that we could translate it in principle to the more formal form of the former proof. This is no different than the difference between written proof and completely formal proof in the sense of formal logic.
> 2 votes

---
Tags: algorithms, online-algorithms
---


title: Help With Writing An Algorithm Formally

text:
# Question
Title: Help With Writing An Algorithm Formally
First off - I'm not a Computer Scientist, I'm a Software Developer - so when it comes to presenting an idea in a formal manner to a Computer Scientist, I have no idea how to do so. As such, I'm wondering if someone would be good enough to show me how to write the algorithm/idea I've outlined below in some form of formal alogrithmic notation, please?

*Part One:*

Say I have a list of 'words' made up from characters of the English alphabet. Essentially, I want to split this list of 'words' up into twenty-six sub-lists, where each sub-list is associated with one letter of the alphabet - *a, b, c, etc*. Each 'word' should be moved to the sub-list associated with the character that the 'word' begins with - so 'apple' would go in the 'a' sub-list, 'banana' would go in the 'b' sublist, etc. **BUT**, I only want to divide my original list up into sub-lists provided that there are at least *X* 'words' in the list that begin with each letter of the alphabet (so if *X* was 2, there would need to be at least two words beginning with 'a', at least two words beginning with 'b', ..., at least two words beginning with 'z', etc.). In essence, it's either one list with all 'words' in it or 26 sub-lists with at least *X* 'words' in it.

*Part Two:*

Assuming I was able to split the list of 'words' up into sub-lists as described in Step One, I then want to further divide each sub-list based on the value of the second character in each 'word'. So there would be an 'aa' sublist, an 'ab' sublist, ..., a 'zz' sublist, etc. Again, I only want to do any further division of the sub-lists provided there are at least *X* 'words' that begin with every possible two-character combination of English alphabet letters - so at least two 'words' beginning with 'aa', two 'words' beginning with 'ab', ..., two words beginning with 'zz', etc. In essence, it's either 26 sub-lists or 676 sub-lists.

*Part Three:*

I want this dividing process to continue (character three, character four, etc.) until it is no longer possible to satisfy the criteria that there are at least X 'words' in each sub-list that 'begin' with every possible combination of the number of characters that are currently under consideration.

For argument's sake at this point, it can be assumed that all 'words' are the same length.

Any help is very much appreciated.

# Answer
> 4 votes
# Computer scientists are almost people

I think your explanation is pretty good. There is not a single formal way to specify an algorithm, except perhaps for pseudocode but as a software developer you are likely already familiar with that. Apart from that, algorithms that don't rely on intricate math are often best explained through text, as you've done.

Perhaps it could do with a bit more formal language however. First, note that what you're describing is more accurately called a data structure than an algorithm. Indeed, you give no method for creating this structure, but rather give a description of what it looks like.

Furthermore, you could (though I argue this is not mandatory) describe the structure more mathematically if you want, defining the various objects used. For example, say we have some set of words $W$, each of which is a string made up of some set of characters $C = \\{a, b, c, \dots\\}$. We'll also define $W\[s\]$ to mean the set of words in $W$ that begin with string $s$. In our case these are English words and characters, but that does not matter for the general case. Now, we can define our data structure recursively as follows (we'll call the structure a "slick" for now, in reference to your username).

A slick $S\_s$ for some set of words $W\[s\]$ denoted $S\_s(W\[s\])$ is defined as a list $\[S\_{s+a}(W\[s+a\]), S\_{s+b}(W\[s + b\]), \dots\]$. A slick on an entire corpus $W$ is defined as $S\_\epsilon(W\[\epsilon\])$ where $\epsilon$ denotes the empty string.

However, if one of the subsets $W\[s+c\]$ for $c \in C$ is not of at least some constant size $k$, $S\_s$ is instead defined as $S\_s(W\[s\]) = W\[s\]$.

Note here that we implicitly define every "subslick" $S\_s$. That is, the part of the slick where every word already starts with some string $s$. We define the whole slick as a special case of the subslick, namely one where every words starts with nothing, which is true for every word. Finally, we denote the stopping condition that if not every prefix is frequent enough, we stop making slicks.

We might be able to make it shorter and more formal by introducing more notation, but this would in my opinion come at the cost of readability. For example, "if one of the subslicks is not of some constant size $k$, then define it this other way" can be turned into $(\exists\_c \\, \[|W\[s+c\]| \< k\]) \rightarrow S\_s(W\[s\]) = W\[s\]$, but I argue that this does not help most readers.

Of course, this all depends on the audience. If you're submitting a paper in computer science with as its primary purpose the establishment of an algorithm or data structure, I would expect an informal explanation as well as a formal one, with absolutely no ambiguity. I would also expect not just a description of the data structure, but an explanation of its usefulness, and mathematical arguments for its properties.

# This is almost exactly a trie

As for the data structure itself, except for the stopping condition this is exactly a trie, a structure that's been around since this paper in 1959. To look for other ideas for formalization, you might want to look for other explanations of the trie on the web.

The difference between the trie (also called prefix tree for obvious reasons) and the slick is that the trie just keeps making tries until there are no more words with a certain prefix. The slick stops significantly earlier, which I'm not sure is a great idea. Indeed, if we're encoding a moderately sized set of English words, we might not find $k$ words that start with an x, and then the data structure collapses entirely. Instead, I'd recommend not collapsing $S\_s$ when $W\[s+c\]$ is small, but rather collapsing $S\_s$ only if $W\[s\]$ is small.

# Answer
> 2 votes
Algorithms are often presented in pseudocode, definitions, informal explanations, and proofs of correctness. Here's an excerpt from an example from CLRS, a widely used algorithms textbook:

Then the pseudocode:

As you can see, the pseudocode uses some math notation mixed with programming notation. It doesn't correspond to any one language but tries to get the point across in a standardish procedural language, which could be implemented relatively straightforwardly in C, FORTRAN, Pascal, Java, Python, etc.

Like ADdV's excellent answer says, if you are seriously presenting the algorithm as a publication to computer scientists, formal justification, such as using induction or loop invariant arguments, is required.

---
Tags: algorithms
---


# Question
Title: Why the Cook-Levin reduction is not a parsimonious reduction?
In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is one in which certificates of an NP language are mapped bijectively on the certificates of SAT. I am not sure why the reduction is already not parsimonious.

The reduction basically converts the snapshots $Z\_1, Z\_2, \dots, Z\_{T(n)}$ ($Z\_i$ contains the state, the symbols of the two tapes currently under head in the $i$th step) of an oblivious NP machine into a SAT formula, where $T(n)$ is the runtime of the NP machine. The main observation used for converting the sequence of snapshots into a SAT formula is that every $Z\_i$ is a function of previous $Z\_i$s.

Following is Cook-Levin's proof from Arora-Barak.

# Answer
> 0 votes
The string $u$ is the certificate for $x$ with respect to $L$ and $M$, while the string $y \circ z$ is the certificate for $\phi\_x$ with respect to $SAT$ and a verifier TM for SAT. $M$ is an oblivious deterministic TM with two tapes - an input tape and a work/output tape. Although I did not find this clearly stated anywhere, it seems reasonable to assume that the output of $M$ is 1 if the final state is $q\_{halt}$, and the contents of the output tape are $1 \Box \Box \ldots$, and the heads are positioned at their initial locations at the left ends of the tape. In Garey and Johnson, the formalization of the Turing machine contains two halt states $q\_Y$ for accept, and $q\_N$ for reject, all other states are designated non-halting - using such a formalization could simplify this reduction; however, Arora and Barak have kept things more general by not focussing on Boolean functions, since the scope of their text is larger.

Any certificate $u$ can be mapped to some certificate $y \circ z$ such that $y = x \circ u$, and $z$ equals the snapshots of $M$ \- this map is clearly injective. Similarly, $y \circ z$ may be mapped to $u$ by extracting the appropriate substring - in this case, let us prove that the map is injective. Assume that two certificates $y\_1 \circ z\_1$ and $y\_2 \circ z\_2$ may be mapped to the same certificate $u$. This implies that $y\_1 = y\_2 = x \circ u$, which in turn implies that $z\_1 = z\_2$ since these strings record the $T(n)$ snapshots of the deterministic TM $M$ starting for the same input $y\_1 = y\_2$. Given these two injective maps, we can infer that the two sets of certificates have the same cardinality, and hence the reduction is parsimonious.

However, the authors seem to think otherwise. Excercise 2.13.a asks the reader to make the reduction parsimonious, and even a hint is provided:

> "Modify the machine M so that it clears up its work tape before outputting a 1 and moves both heads to one end of the tape. Then the final snapshot and head locations are unique."

Note that the suggested modification does not affect the reduction at all! Using our definition of output, we are already assuming that $M$ is doing everything the hint suggests. The only issue I can see is that Condition (4) only examines the last snapshot $z\_{T(n)}$ to determine whether the output was 1 but $z\_{T(n)}$ only captures a small portion of the output tape - I would question whether this is an accurate test for whether $M$ halted and produced the output 1 - that is, I am not sure that the reduction given in the text is correct.

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


# Question
Title: Proving the validity of a sequent using Modus Tollens
Problem: Prove $p \rightarrow (q \vee r), \neg q, \neg r \vdash \neg p$ using Modus Tollens.

I need to prove the validity of the above sequent by using natural deduction. Initially, I didn't read the entire problem, and went the long way by doing an implication-elimination, two negation-eliminations, an or-elimination, and finally a negation-introduction. Then I read the problem and realized I had to use MT, and now I'm stuck. I don't have the greatest grasp on propositional logic and natural deduction. Am I allowed to do the following?

Since I have $\neg q$ and $\neg r$ as my premises, can I use an and-introduction and do $\neg q \wedge \neg r$, which would allow me to immediately use MT to deduce $\neg p$? If not, could someone point me in the correct direction? Thanks.

# Answer
> 0 votes
Modus Tollens is the following rule:

> Given $A \to B$ and $\lnot B$, deduce $\lnot A$.

In your case, you are given $p \to (q \lor r)$, and so $A = p$ and $B = q \lor r$. Therefore you need to prove $\lnot B = \lnot (q \lor r)$. This is *not* the same as $\lnot q \land \lnot r$, though the two are logically equivalent. What you have to do is deduce $\lnot (q \lor r)$ from the premises $\lnot q$ and $\lnot r$.

---
Tags: propositional-logic, natural-deduction
---


# Question
Title: Coming up with loop invariants involving k?
```
void min(arr[], n){
for(i = 0;i < n; ++i)
{
   // Change < to > if you want to find the smallest element
   if(arr[i] > arr[i+1])
       arr[i] = arr[i+1];
}

```

To avoid wording about a "just check my work" question. I will try to explain what I do not understand about this topic of loop invaraints. I have been having the hardest time coming up with the beginning loop variant with respect to the variables and the what they mean in relation to the arrays. So, my question about this code loop invariant is that this program finds the smallest element in the array. My loop invaraiant is At the start of the iteration when i = k, the item at index k is the smallest item in the range from zero to k. Can you tell me both if I have the correct loop invariant and also am I understanding the concept correctly. I believe that I need to relate such variables such as i, and j in loops with the varaible k in relation to what the program is doing. Thank you.

# Answer
> 1 votes
There is a very simple way to determine whether you have the correct loop invariant:

1. Can you prove that it holds when entering the loop?
2. Can you prove that the loop maintains it?
3. Can you deduce correctness of the algorithm using the invariant?

I trust that you can do all these checks yourself.

---
Tags: algorithms
---


# Question
Title: Finding minimum possible cost of road network between cities with distance from capital condition
I have a graph ***G*** containing cities (vertices ***V***) connected by distanced roads (weighted undirected edges ***E***).

**Characteristics of the graph:**

* Each city is connected to the rest of the graph
* Each city has an index value where the index is equal to minimum number of roads you need to use to get to the capital from this city. Capital has index of 0. The cities connected right to the capital will have index of 1 and so on.
* Some of the roads will be selected to be changed into highways, creating some sort of network.

I would like to find minimum possible cost of said network based on these **requirements:**

1. It is possible to travel from any city to capital
2. When travelling from any city to capital, the sequence of indexes of visited cities during travel is non-increasing
3. The highway network has to be minimum possible

---

**What I did so far:**
I understood this does require MST solution and so I am using Prim's algorithm, but that is solving only part of the problem (req. 1. and *possibly* 3.) and I need to add something to my MST algorithm to ensure the 2. requirement is fulfilled, and that is my only problem.

I think starting from the capital city might be the first step (and I do so in Prim's), but how to deal with the indexation based on actual road distance from capital city?

**Examples:**

In the picture  below, fig. a) shows incorrect solution using MST algorithm only – one of the possible MST with weight of 35.
Opposed to this, fig. b) shows one of the possible **correct** solutions with paths with weight of 120.

# Answer
The MST indeed adresses conditions 1 and 3 but not conditions 2. The solution of the global problem (as shown by your example) is not the MST but still a tree.

Let's call $T$ the solution for the input graph $G$. Let's also call $T\_i$ the solution for the problem $G\_i$ which is the subgraph of $G$ containing vertices with range index lower or equal to $i$ (I will use the term "range index" to prevent confusion with the vertex indexing used for Prim's algorithm).

Trivially $T\_0$ and $G\_0$ contain only the capital. Now what about $G\_1$ ?

The cities having a range index of 1 cannot use largest index cities to connect captial. Thus $T\_1$, which is by the way MST of $G\_1$, is a subgraph of $T$.

$T\_{i+1}$ is built the same way using $T\_i$ and $G\_{i+1}$. The edges of $T\_i$ are kept and only the new edges to connect the cities having range index $i+1$ are added using any MST algorithm.
> 1 votes

---
Tags: algorithms, graphs, weighted-graphs, minimum-spanning-tree, spanning-trees
---


# Question
Title: An almost surely finite time game of coin toss where you win with probability $p$
Given a fair coin and a number $p\in(0,1)$. How do you design a game that finishes in a finite number of tosses with probability $1$, and further, with probability $p$ you win the game?

I thought about random walks where head, you add 1, tail you subtract 1. And you want to get to $n$. But that gives an approximation to $p$ and not $p$.

# Answer
Let $x\_1,x\_2,x\_3,\ldots$ be the coin tosses, and let $p=0.y\_1y\_2y\_3\ldots$ be the binary expansion of $p$. Halt once either of the following events happens:

1. $x\_1=y\_1,\ldots,x\_{n-1}=y\_{n-1}$ but $x\_n \< y\_n$. In that case, declare a win.
2. $x\_1=y\_1,\ldots,x\_{n-1}=y\_{n-1}$ but $x\_n \> y\_n$. In that case, declare a loss.

The game halts with probability $1$, since at any step it has a probability of $1/2$ to end. Let us now compute the probability of winning at the $n$'th step. If $y\_n = 0$ then this event has probability $0$, and if $y\_n = 1$ then it has probability $2^{-n}$. In total, the probability to win at the $n$'th step is $y\_n 2^{-n}$. Since these events are disjoint, we deduce that the winning probability is $$ \sum\_{n=1}^\infty y\_n 2^{-n} = p. $$

*What is happening here?* We can imagine the coin being tossed infinitely many times, generating a value $q \in \[0,1\]$ whose binary expansion is $0.x\_1x\_2x\_3\ldots \in \[0,1\]$. Clearly, $q$ is uniformly distributed in $\[0,1\]$. The game is a win if $q \< p$ and a loss if $q \> p$ (the probability that $q = p$ is zero). We can halt the game without generating all digits of $q$ if a prefix of its binary expansion suffices to determine that $q \< p$ or that $q \> p$.
> 1 votes

# Answer
Are you sure this is actually possible? If $p$ is a non-computable number and you had a procedure to design such a game, you could design an algorithm that plays the game repeatedly keeping track of how many times it wins, in such a way that with arbitrarily high probability you get right the first digit of the decimal expansion of $p$, and then the second and so on, which would make $p$ computable.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Recurrence formula for optimal binary search tree
This question is from Section 15.5 of *Introduction to Algorithms* (third edition).

We are given sequence of keys, $ k = \\{ k\_{1},k\_{2},\dots,k\_{n} \\}$, where $k\_{1}\<k\_{2} \<\dots\<k\_{n} $.

For each key $k\_{i}$, where $1\leq i \leq n$, we have a probability $p\_{i}$ that a search will be for $k\_{i}$.

We let the sequence $d =\\{ d\_{0},d\_{1},\dots,d\_{n} \\}$, where $d\_{0}\<d\_{1} \<\dots\<d\_{n} $, be for values not in $k$.

For each key $d\_{i}$, where $0\leq i \leq n$, we have a probability $q\_{i}$ that a search will be for $d\_{i}$.

The goal is to construct an optimal binary search tree.

Let us define $e\[i,j\]$ as the expected cost of searching an optimal binary search tree containing the keys $k\_{i},\dots,k\_{j}$.

Let $w(i,j) = \sum\_{l=i}^{j} p\_{l} + \sum\_{l=i-1}^{j} q\_{l}$.

The book gives the following equation as the recurrence formula for forming the optimal binary search tree: $$ e\[i,j\] = \begin{cases} q\_{i-1} & \text{if } j = i-1, \\ \displaystyle\min\_{i\le r\le j} \\{e\[i,r-1\]+r\[r+1\],j\]+w(i,j)\\} & \text{if } i \leq j. \end{cases} $$

This formula makes sense for $i\leq j$, but I don't understand the case $j = i-1$.

> Why is $e\[i,i-1\] = q\_{i-1}$?

# Answer
Quoting *Introduction to Algorithms*:

> The easy case occurs when $j = i-1$. Then we have just the dummy key $d\_{i-1}$. The expected search cost is $e\[i,i-1\] = q\_{i-1}$.

In slightly more detail, $e\[i,j\]$ is supposed to be the cost of the optimal binary search tree for $k\_i,\ldots,k\_j$. It is important to understand what *cost* means here. The cost is with respect to the following distribution on the input:

* With probability $p\_i$, key $k\_i$ is being searched.
* With probability $q\_i$, a dummy key $d\_i$ between $k\_i$ and $k\_{i+1}$. (When $i = 0$, it is a key smaller than $k\_1$, and when $i = n$, it is a key larger than $k\_n$.)

Unfortunately, the textbook is being extremely sloppy, and never bothers to explain what they mean by "the cost of the optimal binary search tree for $k\_i,\ldots,k\_j$". It seems that they are measuring the expected cost with respect to the stated keys as well as with respect to the dummy keys $d\_{i-1},\ldots,d\_j$. That is, they want to minimize $$ q\_{i-1} \mathit{cost}(d\_{i-1}) + p\_i \mathit{cost}(k\_i) + q\_{i+1} \mathit{cost}(d\_{i+1}) + \cdots + q\_{j-1} \mathit{cost}(d\_{j-1}) + p\_j \mathit{cost}(k\_j) + q\_j \mathit{cost}(d\_j). $$ When $j = i-1$, there are no real keys, but there is a dummy key $d\_{i-1} = d\_j$, and so the cost is $q\_{i-1} \mathit{cost}(d\_{i-1})$. The optimal cost here is clearly $1$, and that's how they get $q\_{i-1}$.
> 0 votes

---
Tags: dynamic-programming, recursion, binary-search-trees
---


# Question
Title: Two increasing functions from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is O(f (n))
Here is the question again : Give an example of two increasing functions f (n) and g(n) from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is O(f (n)).

I tried with several functions such as sine and cosine, but they are not increasing functions but Oscillatory. Then I tried x + sinx and x + cosx. However for sufficiently large coefficients c and n0, they also fail two satisfy the criteria. I am starting to doubt if such pairs of functions even exist !?

# Answer
> 3 votes
Take $f(n) = (2\lfloor\frac{n}{2}\rfloor+1)!$ and $g(n) = (2\lceil \frac{n}{2} \rceil)!$.

For example: $$ \begin{array}{c|ccccc} n&1&2&3&4&5 \\\hline f(n)& 1! & 3! & 3! & 5! & 5! \\\hline g(n)& 2! & 2! & 4! & 4! & 6! \end{array} $$ We have $$ \frac{f(2m)}{g(2m)} = \frac{(2m+1)!}{(2m)!} = 2m+1 \to \infty $$ as well as $$ \frac{f(2m+1)}{g(2m+1)} = \frac{(2m+1)!}{(2m+2)!} = \frac{1}{2m+2} \to 0. $$

# Answer
> 2 votes
Totally inelegant approach:

Start with f, g = 0. Increase f by 3, g by 1, until f(n) \>= 2 g(n). Then increase f by 1, g by 4, until g(n) \>= 3f(n). Then increase f by 5, g by 1 until f(n) \>= 4 g(n) etc.

# Answer
> 0 votes
Let's consider $f,g$ $$f(x)= \begin{cases}{} k^{2k}, & x\in(2k,2k+1)\\ k^{2k+1}, & x\in(2k+1,2k+2) \end{cases} \\ g(x)= \begin{cases}{} k^{2k-2}, & x\in(2k,2k+1)\\ k^{2k+2}, & x\in(2k+1,2k+2) \end{cases} \\ $$ for $k \in \mathbb{N}$

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


title: Regula falsi with error in x-axis

text:
# Question
Title: Regula falsi with error in x-axis
I want the regula falsi to get x +- .0001 so that f(x) = 0. But all the implemetations I see get x so that f(x) +- .0001 = 0 which doesn't make much sense. (f(x) = x^3).

How do I stop the regula falsi method when the error is .0001 on the x-axis?

I have this scilab code:

function salida = falsaposicion(fun, tolerancia, a, b)
   deff("y=f(x)", "y="+fun);
   if (f(a)*f(b)>0) then
       disp("Error");
   end

   cAnt = 1e100
   c =  b - f(b)*((b - a)/(f(b) - f(a)));

   while 0 == 0
       if f(b) - f(a) == 0 then
           disp("Error");
           break;
       end

       if abs(f(c)) < tolerancia then
           break;
       elseif f(a)*f(c) < 0 then
           b = c;
       elseif f(b)*f(c) < 0 then
           a = c;
       end

       cAnt = c;
       c = b - f(b)*((b - a)/(f(b) - f(a)));
   end

   salida = c;
endfunction

disp(falsaposicion("x^3", 0.0001, -6, 3));

```

# Answer
> 1 votes
A loop invariant of *regula falsi* is that $f(a)f(b)\<0$. Under the assumption that $f$ is continuous, this implies that there is a solution $x\_0$ of $f(x0)=0$ inside $(a,b)$, since the eventual output $c$ is also in $(a,b)$, then for any output you have that $|c−x\_0|≤|a−b|$. Therefore, you can add to the breaking condition, instead of it being `abs(f(c))<tolerancia`, to be `abs(f(c))<tolerancia and abs(b-a)<.0001`, or replace it completely by `abs(b-a)<.0001`.

It is true that the distance between $a$ and $b$ doesn't always go to zero. That's the price you pay for converging faster than bisection in some cases. Still, that is the only condition that you have to bound the error, if *regula falsi* is applied by itself, since $c$ could be approaching a root only from one side. What people do is not to apply *regula falsi* by itself, but to mix it, among other methods, with bisection. For example, what is done in Brent's method.

---
Tags: approximation, error-estimation
---


# Question
Title: Encoding two 6-bit positive integers compactly
Is it possible to encode two 6-bit wide positive integers `a` and `b` guaranteed to be in `[0, 63]` in a way that `a` and `b` are recoverable -- in fewer than 12 bits? We could obviously concatenate the binary representations `(a << 6 | b)`. The scheme would have to allow any two arbitrary values within the given range. Can we do better than 12 bits?

# Answer
Suppose that $H\colon \\{0,1\\}^6 \times \\{0,1\\}^6 \to \\{0,1\\}^n$ is such that $a,b \in \\{0,1\\}^6$ can be recovered from $H(a,b)$. In particular, $H(a,b) \neq H(c,d)$ whenever $(a,b) \neq (c,d)$. Since there are $2^{12}$ possible inputs, and the value of $H$ on each of them is different, it follows that the range of $H$ must consist of at least $2^{12}$ different points. Since $\\{0,1\\}^n$ has $2^n$ points, we conclude that $n \geq 12$.
> 3 votes

---
Tags: encoding-scheme
---


# Question
Title: Adaptive step size constrained to a limited number of iterations
I'm solving a differential equation on the form $\ddot x = f( \dot x, x)$ on a microchip within a limited (real world) time frame, hence I want to use an adaptive step size to get as good of a result as possible. However, I only have a limited number of iterations, $N$, to solve the system. If I use the "regular" adaptive time step methods of estimating the local error and adapting the step size there's no guarantee that I will be able to solve the system in $N$ iterations.

Does anyone know where I can find algorithms for this? All I can find are the "regular" adaptive time step algorithms where $N$ isn't limited.

The current solution I have is to assume that the error is proportional to the magnitude of $\ddot x$ and projects a line from $x(t\_0)$ with constant velocity $\dot x = c$ to reach $x(t\_n)$ and then use the differential equation to get the distribution of the magnitude of $\ddot x$ to know where the step size needs to be small and adjust it accordingly.

This projected line obviously is not the real path but the idea is that it will give me a good approximation of how the error changes in the future so that I know if I can "afford" to have a small step size at each given iteration. This method assumes that you have the primitive function of $f(c,x(t))$ with respect to t when c is constant, $x(t)$ is linear and $f^{-1}$ exists. The method could probably be expanded to use constant acceleration to project the path instead of constant velocity, but the idea is the same.

The problem is that I can't find any information on the subject and I highly doubt that my naive initial idea is the best one out there.

# Answer
I've come to the conclusion that it's not worth doing for my application, so I thought I would post my progress here for anyone else who might be interested in this same problem.

My more "proper" solution, which does not put any constraints on the differential equation but instead uses an error estimation for the adaptive steps, more like a traditional approach. For anyone dealing with the same problem or interested in a solution here it goes.

For the Euler method we can assume that the error is: $ \varepsilon = c h^2 $, and that $c \approx | \ddot x\_t - \ddot x\_{t-1}$|. In order to limit the number of iterations we will take we have to make some assumptions about the future. The assumption I made is that we will have some average error when we take an equidistant step, and this error will be constant. So let's define the "future average error" as $\hat \varepsilon = \hat c {\hat h}^2$. Since we assume that the future points will be equidistant we know that $\hat h = l/n$ where $l$ is the remaining length (of time) and $n$ is the remaining number of iterations. We don't know $\hat c$ but after some testing I found that the current average $c$ worked rather well, and an exponentially smoothed $c$ worked even better. Making projections on how $c$ will change based on previous data might yield even better results, but I'm trying to do this with few operations so I don't have time to make any advanced predictions.

Now we have all we need, given the assumption that the best accuracy is reached when the error is constant we can set the two equations equal and get: $c h^2 = \hat c (l/n)^2$ which gives us a step size of:

$h = \sqrt{ \frac{\hat c}{c}} \frac{l}{n}$

This step size alone performs rather well, but we do not have any upper bound on the step size and we will get division by 0 if c is zero (if the acceleration is constant between two points). So we simply introduce a lower bound on c defined by an upper bound on h:

$c\_{min} = \hat c ( \frac{l}{n h\_{max}} )^2$

After some testing I've found that a good value for $h\_{max}$ is $\frac{l}{max(n-1,3)}$

So to recap, for the one who just want to test it the algorithm is as follows:

```
h_max = length/(max(n-1,3))
c = max(abs( a - a_previous ),c_hat*(length/(n*h_max))^2 )
c_hat = alpha*c + (1-alpha)*c_hat

h = sqrt(c_hat/c)*length/n

```

where *a* and *a\_previous* is $\ddot x\_t$ and $\ddot x\_{t-1}$ for the differential equation. If you implement this it's important to remember that *length* and *n* is the remaining length and iterations, not the total, so it needs to be updated every iteration. It's also important to note that *c\_hat* is updated with the current *c* value, I found this to yield much better results.

On to why I don't think it's worth it. During my testing I got a maximum of a 40% decrease in Mean Squared Error compared to the "true" solution (evaluated using many many more points). The error for the final point however was often worse than simple equidistant evaluation, even for 'simple' differential equations like y' = a -y. It was only for differential equations which varied a lot (like those with sinusoidal solutions) which gave an improvement in the accuracy of the final point, and since I'm mostly interested in the accuracy of the final point I think it's worth spending those computational resources on doing more iterations rather than adapting the step size. I can probably cram in twice the number of evaluations instead of doing adaptive step sizes which in my testing was always better than the adaptive strategy.

For anyone who wishes to test this further, the main reason why this method doesn't perform as good as one might expect is because of how $\hat c$ is evaluated. Since it's based on previous values (and heavily skewed toward the current value) the algorithm holds off on small step sizes which often is detrimental to performance. Trying to predict how $\hat c$ will actually look in the future would probably yield much better results and it would be a good place to start exploring further.

TLDR; If you have this problem, just spend the computing resources on more iterations (or higher order methods) instead of advanced methods to adapt the step size.
> 1 votes

---
Tags: numerical-algorithms, error-estimation
---


# Question
Title: Does this LCS algo generate all the CS or only all the LCSs?
The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-calculated, if you go up a tad bit. C\[i\]\[j\] stores the LCSLength for given str1\[1...i\], str2\[1...j\].

*(screenshot, for a quicker reference)*

1. My understanding is that it generates **all** the **common sequences** since either or both *if* conditions at the end are satisfied, which runs the program for the sub-cases. Once the last letters are matched, every string upto that point (with the *current* X\[i\] as the last letter) is printed.

I somewhere fail to digest the algorithm properly and completely. An explanation might help me very much.

2. In the penultimate *if*, does changing writing the piece of code as *R := R $\cup$ backtrackAll(C, X, Y, i, j-1)* (instead of R := backtrackAll(C, X, Y, i, j-1)) change anything? I feel that it doesn't, given it's a top down approach and it only unions with the empty set R = {} above. Note that R is already defined above and the *if* is reached only after going through that empty set definition step, which rules out the possibility of having an error output.

# Answer
> 1 votes
Wikipedia is being sloppy. The procedure returns all LCSs of $X\[1..i\]$ and $Y\[1..j\]$, which corresponds to $C\[i,j\]$. It should mention that in order to obtain all LCSs, we need to set $i=m$ and $j=n$.

If $X\[i\] = Y\[j\]$, then every LCS of $X\[1..i\]$ and $Y\[1..j\]$ is obtained by taking an LCS of $X\[1..i-1\]$ and $Y\[1..j-1\]$, and adding to it $X\[i\] = Y\[j\]$.

If $X\[i\] \neq Y\[j\]$, then every LCS of $X\[1..i\]$ and $Y\[1..j\]$ must be either an LCS of $X\[1..i-1\]$ and $Y\[1..j\]$, or an LCS of $X\[1..i\]$ and $Y\[1..j-1\]$ (or both). If $C\[i-1,j\] \> C\[i,j-1\]$, then only the former are LCSs of $X\[1..i\]$ and $Y\[1..j\]$. If $C\[i-1,j\] \< C\[i,j-1\]$, then only the latter are LCSs of $X\[1..i\]$ and $Y\[1..j\]$. If $C\[i-1,j\] = C\[i,j-1\]$, then both types are LCSs of $X\[1..i\]$ and $Y\[1..j\]$.

This recursive procedure could count the same sequence more than once — this happens for example for the arrays $ab$ and $ac$, where $a$ will be reached twice.

---
Tags: dynamic-programming, recursion, backtracking
---


# Question
Title: What exactly is the difference between a Balanced Binary Search Tree and an AVL tree?
I'm learning some Data Structures and I cannot figure out the difference between the Balanced BST and the AVL Tree. From my understanding, an AVL tree is a balanced tree with the height difference \<= 1.

But then what about the Balanced Binary Search Tree? What's the difference here?

Let's take an example:

I have a sorted array `X = {1,2,3,4,5}` and if I insert each of the values in `X` into a Balanced Binary Search Tree, I get the PreOrder output as `3 1 2 4 5`. However, if I insert each of the values of `X` in an AVL tree, I get the PreOrder output as `2 1 4 3 5`.

I notice that an AVL is always self-balancing, but it seems that a balanced BST is not necessarily an AVL.

I am quite confused about this. Is there something I am missing here?

# Answer
There are some implementations of Balanced Binary Search Trees, also known as Self-balancing Binary Search Trees. One of the aspects that can be considered when balancing a tree is it's subtrees height difference. This height aspect aims to keep the tree as flat as possible. The more flat the tree is, the less levels it will have and the search will be faster.

The implementation that you mentioned reconstructs the entire tree when a new node is inserted, from the root to the leaves. The AVL tree will reorganize (balance) only the subtrees needed to meet its invariant, i.e., the height difference less or equal to one, when a new node is inserted or a existing node is removed.

The pre-order traversal will be different, since these two BBSTs have different implementations! If you test, maybe a red-black tree (another BBST), the preorder will be different too!

The main thing to keep in mind is that the reason of the BBSTs to exist is that they will keep them more flat as possible to speed up the search for nodes. The only traversal that will be equal among them (if they are search trees) is the in-order traversal, that can be also used to sort data.
> 1 votes

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


# Question
Title: Operations without common elements can not be generated using a finite state automata
I heard that some operations involving regexes that do not have common elements can NOT be generated using a finite automata. I do not remember what it was, where it was from, can anyone tell me what that could possibly be?

Edit : I finally managed to find the exact statement. Here it is, below :

*A language (like $(00)^n (11)^n$) can not be generated by an FSM since there is no common character in "00" and "11". We need to keep count of both which is not possible with a finite automata as the count can be infinite.*

# Answer
> 1 votes
The remark by the tutor is very poorly worded. My best guess is that it refers to the following situation. Let $L\_{x,y}$ be the set of all words that have as many copies of $x$ as that of $y$. Then $L\_{0,1}$ is not regular, but $L\_{01,10}$ is regular, since it equals $(0^+1^+)^\*0^+ + (1^+0^+)^\*1^+ + \epsilon$.

# Answer
> 1 votes
One has to differentiate between regex in computer science and regex in real world programming languages. In compsci regular expressions are defined to only recognize regular languages, which are the same languages DFAs can recognize, thereby making DFAs and regex a descriptions of the same class of languages.

In real world application the recognition of regular languages is somewhat limiting which is the reason why many regex libraries introduce operators which allow you to recognize languages that are *not regular*. One such operator is recursion `(?R)` see here for an example using python. Notice that the language in the article is the *balanced parentheses language* which is a well known context free language that is not regular and thus can not be recognized by a DFA.

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


# Question
Title: reducing $CLIQUE$ from decision to search problem
consider the language:$$CLIQUE = \left\\{\langle G,k\rangle \ |\ \text{ $G$ is a graph containing a clique of size at least $k$ } \right\\}$$

> Suppose there's a polynomial time algorithm for $CLIQUE$. I need to show a polynomial time algorithm for finding a clique of size $k$.

Now, the idea is pretty easy if there's only one clique in the graph - You remove each vertex $v\_i$ and query for $CLIQUE(G\_i, k)$.

If there are two cliques in the graph this algorithm *could not* be applied since no matter which vertex will be removed there will always be a clique of size $k$.

An alternative would be removing each one of the ${m}\choose{k}$ but if $k = n/2$ for example, that wouldn't be a polynomial time algorithm anymore.

So my question is, can we solve this problem for the general case where there might be multiple cliques?

# Answer
> 3 votes
Keep removing vertices until the graph no longer contains a clique of size $k$, and let $v$ be the last vertex that you removed. It follows that there is some $k$-clique which contains $k$. Remove all vertices from the graph other than neighbors of $v$ (so $v$ itself is also removed), and recursively find a $(k-1)$-clique in the new graph. Add $v$ to this clique to create the desired $k$-clique.

The algorithm can also be formulated iteratively:

1. Let $C = \emptyset$ (this will be the clique).
2. Let $\ell = k$ (the current size of the clique).
3. Go over all vertices $v$ in the graph:
    * Check if after removing $v$ from the graph, the new graph still contains an $\ell$-clique.
    * If so, continue to the next vertex.
    * Otherwise, add $v$ to $C$, decrease $\ell$, and remove from the graph all vertices other than the neighbors of $v$.
4. Return $C$.

# Answer
> 0 votes
I think you can "strip the graph" until a $k$-clique remains instead of "building a $k$-clique":

1. Initially check for a $k$-clique, if none exists, return that answer.
2. Go through the vertices $v\_1, v\_2, \dotsc, v\_n$. \[One can terminate once $k$ vertices remain, but this is optional.\]

At each iteration, delete vertex $v\_i$ and check for a $k$-clique.

* If no $k$-clique exists in the remaining graph, then $v\_i$ was "essential", i.e., in every $k$-clique of the graph prior to deletion, so add $v\_i$ back!
    * If a $k$-clique still does exist, leave $v\_i$ deleted

I'm quite sure this algorithm can be proven correct using the "essential vertex" definition. In contrast to the algorithm in Yuval's answer, the clique parameter $k$ stays the same throughout. So my algorithm is potentially less efficient, but maybe a tad easier to understand.

---
Tags: algorithms, time-complexity, polynomial-time, clique
---


# Question
Title: Characterization about Kleene Closure, when is a language $L=L^*$?
I'm trying to find a characterization of when $L=L^\*$.

I think I have one, but maybe is trivial, but I don't know if the proof is correct.

Claim: $L=L^\* \Leftrightarrow L=LL$.

Proof:

If $L=L^\*$ then is easy to see $LL \subseteq L$ so $L=LL$.

The other implication is in which I have doubts, I used a simple chain of equalities $$L=LL=\cdots=L^n=\cdots= \bigcup\_{i\geq 0}L^i=L^\*.$$

I would like to know if there is something wrong and specially if there's another characterization which is less trivial.

# Answer
> 2 votes
What your argument actually shows is $$ L = L^\* \Rightarrow L=L^2 \Rightarrow L = L^+. $$ Indeed, suppose that $L = L^\*$. On the one hand, $L^2 \subseteq L^\* = L$. On the other hand, since $\epsilon \in L$, we have $L = \epsilon L \subseteq L^2$.

Next, suppose that $L = L^2$. Inductively, $L = L^n$. In particular, if $w \in L^+$ then $w \in L^n$ for some $n$, and so $w \in L$, showing that $L^+ \subseteq L$; and $L \subseteq L^+$ trivially holds.

If $L = L^+$ then we cannot conclude that $L = L^2$. For example, $a^+ = (a^+)^+$ but $a^+ \neq a^+a^+$.

If $L = L^2$ then we cannot conclude that $L = L^\*$. For example, $\emptyset = \emptyset^2$ but $\emptyset \neq \emptyset^\*$.

However, it is possible to prove the following:

* If $L = L^+$ and $\epsilon \in L$ then $L = L^2$. This shows that if $\epsilon \in L$, then $L = L^+ \Leftrightarrow L = L^2$.
* If $L \neq \emptyset$ then $L = L^2 \Rightarrow L = L^\*$. This shows that if $L \neq \emptyset$, then $L = L^\* \Leftrightarrow L = L^2$.

Indeed, if $L = L^+$ and $\epsilon \in L$ then $L^2 \subseteq L^+ = L$, and $L \subseteq \epsilon L \subseteq L^2$.

Next, if $L \neq \emptyset$ and $L = L^2$ then let $w$ be a word of smallest length in $L$. Since $L = L^2$, we can write $w = xy$, where $x,y \in L$. By assumption, $|x|=|y|=|w|$, and so $|w| = 2|w|$, implying that $w = \epsilon$. Together with $L^+ \subseteq L$, this shows that $L^\* \subseteq L$, and so $L = L^\*$.

---

Another nice characterization is: $$ L = L^\* \Leftrightarrow L = M^\* \text{ for some language } M. $$ One implication is trivial. In the other direction, if $L = M^\*$ then $L^\* = (M^\*)^\* = M^\* = L$.

This characterization remains true if we impose restrictions on $M$, for example $M \cap M^2 = \emptyset$. Indeed, suppose that $L = L^\*$, let $\tilde L = L \setminus \\{\epsilon\\}$, and let $M = \tilde L \setminus \tilde L^2$. Note that $M^2 \subseteq \tilde L^2$, and so $M \cap M^2 = \emptyset$. Also, clearly $M^\* \subseteq \tilde L^\* = L$. On the other hand, we can prove inductively that $L \subseteq M^\*$.

Indeed, let $w \in L$. If $w = \epsilon$ then clearly $w \in M^\*$. Otherwise, $w \in \tilde L$. If $w \in M$ then clearly $w \in M^\*$. Otherwise, $w \in \tilde L^2$, that is, $w = xy$, where $|x|,|y| \< |w|$. By induction, $x,y \in M^\*$, and so $w = xy \in M^\*$.

---
Tags: formal-languages, kleene-star
---


# Question
Title: Decidability of a problem concerning polynomials
I have come across the following interesting problem: let $p,q$ be polynomials over the field of real numbers, and let us suppose that their coefficients are all integer (that is, there is a finite exact representation of these polynomials). If needed, we may suppose that the degree of both polynomials is equal. Let us denote by $x\_p$ (resp. $x\_q$) the greatest absolute value of some (real or complex) root of the polynomial $p$ (resp. $q$). Is the property $x\_p = x\_q$ decidable?

If not, does this property hold for some restricted families of polynomials? In the context from which this problem arises, the polynomials are characteristic polynomials of matrices, and their roots are eigenvalues.

I am aware of some numerical algorithms for computing roots of polynomials / eigenvalues, however these seem to be of no use here, since the output of these algorithms is only approximate. It seems to me that computer algebra might be useful here, however, unfortunately, I do not have almost any knowledge in that field.

I am not searching for a detailed solution to this problem, however any intuition and ideas where to search for the solution would be helpful.

Thank you in advance.

# Answer
> 6 votes
I'm not knowledgeable in that field either, but I think I can provide a non-constructive answer.

The first-order theory of real closed fields is decidable. Your problem can be stated as a system of algebraic equations and inequations over the real algebraic numbers. Consider $2 (\deg P + \deg Q)$ variables $x\_1,\ldots,x\_{\deg P}, y\_1,\ldots,y\_{\deg P}, x'\_1,\ldots,x'\_{\deg P}, y'\_1,\ldots,y'\_{\deg P}$. You want to know whether the following system is satisfiable: $$\begin{align\*} P(x\_j+i\\,y\_j) &= 0 & \text{for \\(1 \le j \le \deg P\\)} \\ Q(x'\_k+i\\,y'\_k) &= 0 & \text{for \\(1 \le k \le \deg Q\\)} \\ x\_j^2 + y\_j^k &\le x\_1^2 + x\_2^2 & \text{for \\(2 \le j \le \deg P\\)} \\ {x'}\_j^2 + {y'}\_j^k &\le {x'}\_1^2 + {x'}\_2^2 & \text{for \\(2 \le k \le \deg Q\\)} \\ x\_1^2 + y\_1^2 = {x'}\_1^2 + {y'}\_1^2 \\ \end{align\*}$$

The first two equation families express that the $x\_j+i\\,y\_j$ and $x'\_k+i\\,y'\_k$ are roots of the polynomials, the next two inequation families express that $x\_1+i\\,y\_1$ and $x'\_1+i\\,y'\_1$ have the largest absolute value, and the last inequation compares these largest absolute values.

It is decidable whether this system is satisfiable: your problem is decidable. However, this statement is probably not the most efficient way to go about it.

A more useful answer probably involves the theory of Gröbner bases. If you're trying to solve that problem for yourself, I think reading the first few chapters of any computational algebra book will give you the requisite background. If you're just aiming to solve your underlying problem, there is probably an off-the-shelf algorithm you can implement.

# Answer
> 2 votes
I may be wrong about this: I am also not very knowledgeable in this field (where are the experts!?), but I believe I have a reasonably fast algorithm for what you are asking.

I am going to suppose, for simplicity, that all the roots are real. Find an interval bound on the root of $P$ with highest absolute value (i.e. an interval $I$ such that $x\_P\in I$ and $x\_P'\notin I$ for all other roots of $P$). Such an interval can be found by the combined use of dichotomy and Sturm's theorem. Now compute the polynomial GCD $R$ of $P$ and $Q$. Verify that $R$ has a root in $I$ (again with Sturm's theorem).

If I am not mistaken, $R$ has such a root if and only if $P$ and $Q$ have a common root in $I$, which in turn is only possible if $x\_P$ is a root of $Q$. Both the application of Sturm's theorem and the GCD are rather fast (not more than quadratic in the size of the polynomials in fact).

This is just a sketch, but it doesn't take much to turn this into a *bona fide* algorithm, in fact I suspect that the use of Maple or Mathematica would make this trivial.

# Answer
> 2 votes
An effective algorithm could be the following:

1. Replace each polynomial by their quotient with their GCD with their own derivative. This is just to make possible multiple roots simple, in case the inputs had them.
2. Replace the polynomials $P$ and $Q$ by polynomials by the resultant $R(t)$ of $P(x)$ and $x^{\deg(P)}P(t/x)$ and the resultant $S(t)$ of $Q(x)$ and $x^{\deg(Q)}Q(t/x)$, respectively. These have roots equal to the products of pairs of roots of $P$, the first one, and pairs of roots of $Q$, the second one. In particular, the root $x\_R$ of $R$ of largest absolute value would be $x\_p\overline{x\_p}=|x\_p|^2$ and that for $S$ would be $x\_S=|x\_q|^2$. Now the original problem has become to determine if $R$ and $S$ have their largest non-negative real root in common.
3. We can once again make the roots of $R$ and $S$ simple as in Step 1.
4. Compute the gcd $D$ of $R$ and $S$ and isolate the largest non-negative root of $R$, $S$ and $D$. This means to obtain intervals $I\_R$, $I\_S$ and $I\_D$ such that $x\_R$ is the only root of $R$ in $I\_R$, $x\_S$ is the only root of $S$ in $I\_S$ and $x\_D$, the largest real root of $D$ is the only one in $I\_D$. This can be done using Vincent's theorem or Sturm's theorem. The former is more efficient, while the second is the one taught more often in school. The interval $I\_D$ isolating the root of $D$ can be shrank arbitrarily small using Bisection method, for example, until it is either contained in the intersection $I\_R\cap I\_S$ or is disjoint with it. In the latter case we output false (note that this case contains the case in which $I\_R\cap I\_S=\emptyset$) and in the former we output true. Observe that if $I\_D\subset I\_R\cap I\_S$, then the largest root of $D$, which is common for $R$ and $S$ must be the root of $R$ in $I\_R$ and the root of $S$ in $I\_S$. Therefore, the largest roots of $R$ and $S$ are the same.

---
Tags: computability, undecidability, computer-algebra
---


title: BVH construction without sorting

text:
# Question
Title: BVH construction without sorting
Common algorithms for creating bounding-volume-hierarchies (BVH) rely on grouping primitives together that are not necessarily adjacent in memory. This is either done by rearranging the primitives directly or using an index which is then sorted. What if we are not allowed to change the order of the primitives? More formally:

Let $P=\\{p\_1, p\_2, ..., p\_k\\}$ be an ordered set of primitives. A BVH can be constructed by splitting the set of indices $I=\\{1,2,...,k\\}$ into two subsets $I\_l$ and $I\_r$ so that $I\_l\cap I\_r=\emptyset$ and $I\_l \cup I\_r=I$. $I\_l$ and $I\_r$ correspond to the indices of all primitives in the left and right child node of the root node. This procedure then repeats recursively for $I\_l$ and $I\_r$ and so on. Now add the additional constraint that $\forall i \in I\_l \forall j \in I\_r(i\<j)$. This prevents rearranging and makes the problem quite interesting in my opinion.

The quality of the best achievable BVH without rearranging primitives depends heavily on the initial order of the primitives. Instead of choosing a spatial split position, for example using the surface area heuristic, we are restricted to choosing a *split index* instead. My guess is that this would make agglomerative clustering algorithms much more attractive, as only adjacent primitives can be clustered together, not arbitrary pairs of primitives.

Has this problem been studied in the literature before?

# Answer
Just some pointers:

* I remember seeing a paper about kd-trees being executed on a GPU, which I think implied them being presorted and then moved into GPU memory. Kd-Trees are not BVHs though.
* Also, there are bulkloaded R-Trees (R-Trees are basically BVHs), such as the STR-R-Trees (sort-tile-recurse) which pre-sort primitives, but not necessarily with memory locality in mind, but that could easily be achieved.
* Finally, there is the PH-Tree (disclaimer: I wrote the paper about it). It stores all geometric data for each node in a single byte-stream for this node (maximum memory locality), however, the parent and children of a node are not necessarily neighbors in memory (the actual implementation, e.g. V13, uses object pooling, so many nodes are likely to be close in memory, but that is not a given, let alone scientifically evaluated. Also, the PH-Tree is not a BVH, it is more like a quadtree. Also, the PH-Tree has come a long way since the original version, it now supports rectangles/boxes (the original paper only mentions points).
> 2 votes

---
Tags: algorithms, trees, graphics
---


# Question
Title: Is Rice's Theorem equivalent to the Halting problem?
As I understand it Rice's Theorem seems to imply the existence of the Halting problem. That is, with Rice's Theorem, we can prove that the Halting problem is undecidable. However, to me, it seems like one could write a proof using that the Halting problem is undecidable to show Rice's Theorem. I'm not exactly sure how one would go about proving such a thing (though it seems by contradiction would be the natural thing to do), but it *feels* to me that that it should be possible?

# Answer
Yes, you can prove Rice's theorem by reduction from the Halting problem. See https://en.wikipedia.org/wiki/Rice%27s\_theorem#Proof\_by\_reduction\_from\_the\_halting\_problem.

The reverse direction is also provable and is trivial.

In some sense all statements that true and provable are equivalent, in the sense that you can prove any by starting from any other, but that probably isn't a useful observation.
> 2 votes

---
Tags: halting-problem, rice-theorem
---


# Question
Title: What is a distributed algorithm for generating random "private" pair-matchings?
Say you have 2N named peers (agents) able to address each other by their name and communicate freely among them. What distributed algorithm could they use in order to randomly pair up? The final situation would be that the agents were able to organize themselves in N random couples. On different runs the random couples should be different.

Important: the algorithm should be "private" in the following sense: at the end of the round, each agent should only know the name of agent it was paired with.

It's also important that the agents have no possible way to influence who they end up paired with.

# Answer
Let's assume the agents are labeled $\[0, n)$. Let $w \> 2$ be a small constant, e.g. 4. Let $F\_k(x)$ be an oblivious pseudo-random function (OPRF).

Let each agent generate random value $s\_i$, announce $H(s\_i)$ and then choose $r = \bigoplus\_i s\_i$ to ensure a fair random shared seed (peers checking the hashes).

Initially agent $i$ chooses $X\_i = i$. Then, some rounds take place. Use the chosen seed to derive a different $P\_r$ and $w$ agents $A\_{r,0}, A\_{r,1}, \cdots, A\_{r,w-1}$ for each round. Then, in round $r$ every agent computes

$$X'\_i = (P\_r - X\_i) \bmod n$$ $$\hat X\_i = \max(X\_i, X'\_i)$$ $$p = H(\hat X\_i) \bmod w$$ $$b =\text{get-secret}\left(p, r, \hat{X\_i}\right) \bmod 2$$

where $\text{get-secret}(p, r, \hat{X})$ securely contacts agent $A\_{r,p}$ and uses the OPRF primitive to compute $F\_{K\_{p,r}}(\hat{X})$, where $K\_{p,r}$ is some never-shared secret round key generated (and stored) by agent $A\_{r,p}$. Then, at the end of the round iff $b = 1$ the agent replaces $X\_i$ with $X'\_i$.

After the round is over the $w$ chosen agents $A$ can (and should) communicate to ensure no one cheated and asked for more than one secret. This ensures everyone only has partial information. If you force the $\text{get-secret}$ requests to be signed by agent $i$ one can even provide evidence another agent tried to cheat.

Do this for a sufficient* number of rounds and the result is that each agent $i$ has a value $X\_i$ such that there is a permutation $\sigma(i) = X\_i$, yet every agent only knows their own $\sigma(i)$, and is deeply unsure about anyone else's $\sigma(j)$.

However, this just gives us a secret random permutation. But we can use this to get a pairing. Note that if we let $g(i) = i \oplus 1$ (where $\oplus$ is XOR) then $f(i) = \sigma^{-1}(g(i))$ is a pairing (assuming zero-indexed permutations).

How can we compute $\sigma^{-1}$? By noting that each round is it's own inverse, each agent sets $X\_i = g(X\_i)$, and we run all the rounds again, in reverse order (with the same $P,A$ and $K$ values), again ensuring that no agent requests too many secrets. The end result is that $X\_i$ contains the partner for each agent.

---

* The technique above is inspired by sometimes recurse shuffle. Read the paper for more ideas, and to get some bounds for what is sufficient.
> 2 votes

---
Tags: algorithms, distributed-systems, network-topology, agent-based-computing
---


# Question
Title: Solving $T(n) = 3T(\frac{n}{3})+\sqrt{n}$ using master method
How can I use the master's method in order to solve the recurrence formula $T(n)=3T(\frac{n}{3})+\sqrt{n}$ ?

# Answer
Taking $n=3^k$ we have $$T(n) =3 T(n/3) + \sqrt{n} =3^2T\left(\frac{n}{3^2}\right) +3\sqrt{\frac{n}{3}}+ \sqrt{n} =\\ =3^3T\left(\frac{n}{3^3}\right) +3^2\sqrt{\frac{n}{3^2}}+3\sqrt{\frac{n}{3}}+ \sqrt{n} = \cdots=\\ =3^kT\left(\frac{n}{3^k}\right)+3^{k-1}\sqrt{\frac{n}{3^{k-1}}}+\cdots +3\sqrt{\frac{n}{3}}+ \sqrt{n} =\\ =3^kT(1)+\sqrt{n}\left( (\sqrt{3})^{k-1}+\cdots + \sqrt{3} +1\right) =\\ = 3^kT(1)+\sqrt{n}\frac{1-(\sqrt{3})^{k}}{1-\sqrt{3}}=\\ =\sqrt{n}T(1)+\sqrt{n}\frac{1-\sqrt{n}}{1-\sqrt{3}} \in O(n) $$
> 1 votes

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


# Question
Title: Solving T(n) = 3T(n/3)+sqrt(n) in terms of  or O notions using master method
Please help me solve it in terms of Theta or Big O

# Answer
> 0 votes
Based on the Wikipedia article I would say it is $\theta(n)$. Case 1.

https://en.wikipedia.org/wiki/Master\_theorem\_(analysis\_of\_algorithms)#Generic\_form

$a=b=3$ and $c\_{crit} = 1$. $f(n)$ has exponent $c=\frac 1 2$ since $f(n)={\sqrt n}=n^\frac 1 2$. So, $T(n)=\theta(n)$ by Case 1 because $c \< c\_{crit}$.

Bobby

---
Tags: master-theorem
---


# Question
Title: The Communication Complexity of Majority, What does Bob send to Alice? Can Bob just wait for Alice's input?
I'm following along the examples in https://people.csail.mit.edu/rrw/6.045-2020/note-cc.pdf and in specifically the following text:

> What’s a good protocol for computing MAJORITY? The natural thing to do is to have Alice and Bob send the vote counts! Over multiple rounds, when it’s Alice’s turn, she sends bits of the integer $N\_x$ which is the number of 1s in $x$, Bob computes $N\_y$ which is the number of 1s in $y$, and Bob sends 1 to Alice if and only if $N\_x+N\_y$ is greater than $n$. (Note the total number of voters is $2n$.) If Alice sends $N\_x$ encoded in binary, this takes $O(\log n)$ rounds. We therefore have:

If Alice is sending her total number of 1s over $\approx \log n$ bits to Bob ... what is Bob sending in back in return before the Alice is done with her input? I assumed or thought that in communication complexity, Alice and Bob are always taking turns back and forth right? Can Bob not send anything and just wait for Alice to send the $\log n$ bits?

# Answer
> 3 votes
Yes it's perfectly fine for one player to send multiple bits while the other waits. In fact, "the" trivial upper bound on communication complexity is having one party send its input to the other one, who can then compute the output locally (although note that there are some very nice and non-trivial probabilistic algorithms -- e.g. for EQ -- even for *one-way communication*, where Alice can talk to Bob but not the reverse). A deterministic communication protocol specifies, as a function of the transcript so far, if Alice or Bob should speak next. Additionally it always specifies when the communication has ended.

Ryan Williams' notes, which you linked, deals at first with the simplified setting:

> In general, Alice and Bob will speak one bit each, in rounds. Alice will always start the communication, and speak one bit in odd-numbered rounds. Bob will always speak a bit in even-numbered rounds.

If you only care about communication complexity and not round complexity, you can replace the above with "Alice and Bob will speak **at most** one bit each, in rounds \[...\]" to capture the more general case.

---
Tags: communication-complexity
---