# Question
Title: Why do more powerful programming languages tend to have slower implementations?
I was reading this article. The author talks about "The Blub Paradox". He says programming languages vary in power. That makes sense to me. For example, Python is more powerful than C/C++. But its performance is not as good as that of C/C++.

Is it always true that more powerful languages must **necessarily** have lesser **possible** performance when compared to less powerful languages? Is there a law/theory for this?

# Answer
**TL;DR:** Performance is a factor of **Mechanical Sympathy** and **Doing Less**. Less *flexible* languages are generally doing less and being more mechanically sympathetic, hence they generally perform better *out of the box*.

### Physics Matter

As Jorg mentioned, CPU designs today co-evolved with C. It's especially telling for the x86 instruction set which features SSE instructions specifically tailored for NUL-terminated strings.

Other CPUs could be tailored for other languages, and that may give an edge to such other languages, but regardless of the instruction set there are some hard physics constraints:

* The size of transistors. The latest CPUs feature 7nm, with 5nm being experimental. Size immediately places an upper bound on density.
* The speed of light, or rather the speed of electricity in the medium, places on an upper bound on the speed of transmission of information.

Combining the two places an upper bound on the size of L1 caches, in the absence of 3D designs – which suffer from heat issues.

**Mechanical Sympathy** is the concept of designing software with hardware/platform constraints in mind, and essentially to play to the platform's strengths. Language Implementations with better Mechanical Sympathy will outperform those with lesser Mechanical Sympathy on a given platform.

A critical constraint today is being cache-friendly, notably keeping the working set in the L1 cache, and typically GCed languages use more memory (and more indirections) compared to languages where memory is manually managed.

### Less (Work) is More (Performance)

There's no better optimization than removing work.

A typical example is accessing a property:

* In C `value->name` is a single instruction (`lea`).
* In Python or Ruby, the same typically involves a hash table lookup.

The `lea` instruction is executed in 1 CPU cycle, an optimized hash table lookup takes at least 10 cycles.

### Recovering performance

Optimizers, and JIT optimizers, attempt to recover the performance left on the table.

I'll take the example of two typical optimizations for JavaScript code:

* NaN-tagging is used to store a double OR a pointer in 8 bytes. At run-time, a check is performed to know which is which. This avoids boxing doubles, eliminating a separate memory allocation and an indirection, and thus is cache-friendly.
* The V8 VM optimizes dynamic property lookups by creating a C-like struct for each combination of properties on an object, hence going from hash table lookup to type-check + `lea` – and possibly lifting the type-check much earlier.

Thus, to *some extent*, even highly flexible languages can be executed efficiently... so long as the optimizer is smart enough, or the developer makes sure to massage the code to just hit the optimizer's sweet spot.

### There is no faster language...

... there are just languages that are easier to write fast programs in.

I'll point to a serie of 3 blog articles from 2018:

I think the latter article is the key point. More flexible languages can be made to run efficiently *with expert's knowledge, and time*. This is costly, and typically brittle.

The main advantage of less flexible languages – statically typed, tighter control on memory – are that they make optimizing their performance *more straightforward*.

**When the language's semantics already closely match the platform sweet spot, good performance is straight out of the box.**
> 8 votes

# Answer
This is simply not true. And part of why it's false is that the premise isn't well formed.

There is no such thing as a fast or slow language. The expressive power of a language is purely a function of its semantics. It is independent of any particular implementation.

You can talk about the performance of code generated by GCC, or about the performance of the CPython interpreter. But these are specific implementations of the language. You could write a very slow C compiler, and you can write Python interpreters that are quite fast (like PyPy).

So the answer to the question of "is more power necessarily slower" is no, purely because you or I can go write a slow C compiler, that has the same expressive power as GCC, but that is slower than Python.

The real question is "why do more powerful languages tend to have slower implementations." The reason is that, if you're considering the C vs Python, the difference in power is *abstraction*. When you do something in Python, there is a lot more that is implicit that is happening behind the scenes. More stuff to do means more time.

But there's also lots of social elements at play. People who need high performance choose low level languages, so they have fine grained control of what the machine is doing. This has led to the idea that low level languages are faster. But for most people, writing in C vs Python will have pretty comparable performance, because most applications don't require that you eke out every last millisecond. This is particularly true when you consider the extra checks that are manually added to program defensively in C. So just because lots of specialists have built fast things in C and C++ doesn't mean they're faster for everything.

Finally, some languages have zero cost abstraction. Rust does this, using a type system to ensure memory safety without needing runtime garbage collection. And Go has garbage collection, but it's so fast that you get performance on par with C while still getting extra power.

The TLDR is that more powerful languages are sometimes faster in some cases, but this is not a firm rule, and there are exceptions and complications.
> 56 votes

# Answer
> Is it always true that more powerful languages must **necessarily** have lesser **possible** performance when compared to their less powerful counterparts? Is there a law/theory for this?

First off, we need to make one thing clear: languages don't have "performance".

A particular program written in a particular programming language executed on a particular machine in a particular environment under particular conditions using a particular version of a particular implementation of the programming language has a particular performance. This does not mean that all programs written in that language have a particular performance.

The performance that you can attain with a particular implementation is mostly a function of how many resources, how much money, how many engineers, etc. are invested to make that implementation fast. And the simple truth is that C compilers have more money and more resources invested in them than Python implementations. However, that does not mean that a Python implementation cannot be fast. A typical Python implementation has about as many full-time engineers as a typical C compiler vendor has full-time custodians that re-fill the developers' coffee machines.

Personally, I am more familiar with the Ruby community, so I will give some examples from there.

The `Hash` class (Ruby's equivalent to Python's `dict`) is written in 100% C in YARV. In Rubinius, however, it is written (mostly) in Ruby (relying only on a `Tuple` class that is partially implemented using VM primitives).

The performance of `Hash`-intensive benchmarks running on Rubinius is not significantly worse than running on YARV, which means that at least for *those* particular combinations of benchmark, language, operating system, CPU, environment, load, etc. Ruby is about as fast as C.

Another example is TruffleRuby. The TruffleRuby developers set up an interesting benchmark: they found two Ruby libraries that use lots Ruby idioms that are thought to be notoriously hard to optimize, such as runtime reflection, dynamically calculating method names to call, and so on. Another criterion they used, was that the Ruby library should have an API compatible replacement written as a YARV C extension, thus indicating that the community (or at least one person in it) deemed the pure Ruby version too slow.

What they then did, was create some benchmarks that heavily rely on those two APIs and run them with the C extensions on YARV and the pure Ruby versions on TruffleRuby. The result was that TruffleRuby could execute the benchmarks on average at 0.8x the performance of YARV with the C extensions, and at best up to 21x that of YARV, in other words, TruffleRuby was able to optimize the Ruby code to a point where it was on average comparable to C, and in the best case, over 20x faster than C.

\[I am simplifying here, you can read the whole story in a blog post by the lead developer: \*Pushing Pixels with JRuby+Truffle\].

That does, however, not mean that we can simply say "Ruby is 20x faster than C". It *does*, however, show that clever implementations for languages like Ruby (and Python, PHP, ECMAScript, etc. are not much different in that regard) can achieve comparable, and sometimes even better, performance than C.

There are more examples that demonstrate how throwing money at the problem increases performance. E.g. until companies like Google started to develop entire complex applications in ECMAScript (GMail, Google Docs, Google Wave \[RIP\], MS Office online, etc.), nobody *really* cared about ECMAScript performance. Sure, there were browser benchmarks, and browser vendors tried to improve them bit by bit, but there was no serious effort to build a *fundamentally high-performance* ECMAScript engine. Until Google built V8. Suddenly, all other vendors also invested heavily in performance, and within just a few years, ECMAScript performance had increased by a factor of 10 across all implementations. But the language had not changed *at all* in that time! So, the *exact same language* suddenly became "10 times faster", just by throwing money at it.

This should show that performance is not an inherent characteristic of the language.

One last example is Java. The original JVM by Sun was dog-slow. Along came a couple of Smalltalk guys who had developed a high-performance Smalltalk VM (the Animorphic Smalltalk VM) and noticed that Smalltalk and Java were very similar, and they could easily build a high-performance JVM using the same ideas. Sun bought the company (which is ironic, because the same developers had already built the high-performance Self VM based on the same ideas while employed at Sun, but Sun let them go just a couple of years earlier because they wanted to focus on Java and not Self as their new language), and the Animorphic Smalltalk VM became the Sun HotSpot JVM, still the most widely-used JVM to date.

(Interestingly, the team that built V8 includes key people of the team that built HotSpot, and the ideas behind V8 are – not surprisingly – also based on the Animorphic Smalltalk VM.)

Lastly, I would also like to point out that we have only talked about languages and language implementations (interpreters, compilers, VMs, …) here. But there is a whole environment around those. For example, modern CPUs contain quite a lot of features that are specifically designed to make C-like languages fast, e.g. branch prediction, memory prefetching, or memory protection. None of these features really help languages like Java, ECMAScript, PHP, Python, or Ruby. Some (e.g. memory protection) even have the potential to slow them down. (Virtual memory can impact garbage collection performance, for example.) The thing is: these languages are *memory-safe* and *pointer-safe*, they don't need memory protection because they fundamentally do not allow the operations that memory protection protects agains in the first place!

On a CPU and an OS that were designed for such languages, it would be much easier to achieve higher performance. If you *really* wanted to do a fair benchmark between, say, C and Python, you would have to run the Python code on a CPU that has received just as many optimizations for Python as our current mainstream CPUs have for C.

You might find some more interesting information in these questions:
> 20 votes

# Answer
In general, it's about what the language and its implementors are trying to do.

C has a long culture of keeping things as close to the hardware as possible. It doesn't do anything that could easily be translated into machine code at compile time. It was intended as a multi-platform kind of low level language. As time went on (and it was a *lot* of time!), C became sort of a target language for compilers in turn - it was a relatively simple way to get your language to compile for all the platforms that C compiled for, which was a lot of languages. And C ended up being the API-system of choice for most desktop software - not because of any inherent qualities in the way C calls things or shares header files or whatever, but simply because the barrier to introducing a new way is very high. So again, the alternatives usually sacrifice performance for other benefits - just compare C-style APIs with COM.

That isn't to say that C wasn't used for development, of course. But it's also clear that people were well aware of its shortcomings, since even people doing "hard-core" stuff like OS development always tried to find better languages to work with - LISP, Pascal, Objective-C etc. But C (and later C++) remained at the heart of most system-level stuff, and the compilers were continuously tweaked to squeeze out extra performance (don't forget there's ~50 years of C by now). C wasn't significantly improved in capabilities over that time; that was never seen as particularly important, and would conflict with the other design pillars.

Why do you design a new language? To make something better. But you can't expect to get *everything* better; you need to focus. Are you looking for a good way to develop GUIs? Build templates for a web server? Resolve issues with reliability or concurrency? Make it easier to write *correct* programs? Now, out of some of those, you may get performance benefits. Abstraction usually has costs, but it can also mean you can spend more of your time performance tweaking small portions of code.

It's definitely not true that using a low-level language (like C) *will* net you better performance. What *is* true, is that if you really really want to, you *can* reach the highest performance with a low-level language. As long as you don't care about the cost, maintainability and all that. Which is where economies of scale come in - if you can have a 100 programmers save performance for 100M programmers through a low-level tweak, that might be a great pay off. The same way, a lot of smart people working on a good high-level language can greatly increase the output of a lot more people using that language.

There is a saying that a sufficiently powerful compiler will be able to eliminate all the costs of high-level languages. In some sense, it's true - every problem eventually needs to be translated to a language the CPU understands, after all. Higher level abstractions mean you have fewer constraints to satisfy; a custom .NET runtime, for example, doesn't *have* to use a garbage collector. But of course, we do not have unlimited capacity to work on such compilers. So as with any optimisation problem, you solve the issues that are the most painful to you, and bring you the most benefit. And you probably didn't start the development of a new, high level language, to try to rival C in "raw" power. You wanted to solve a more specific problem. For example, it's really hard to write high-performance concurrent code in C. Not *impossible*, of course. But the "everything is shared and mutable by default" model means you have to either be extremely careful, or use plenty of guards everywhere. In higher level languages, the compiler or runtime can do that for you, and decide where those can be omitted.

More powerful programming languages tend to have slower implementations because fast implementations were never a priority, and may not be cost effective. Some of the higher level features or guarantees may be hard to optimise for performance. Most people don't think performance should trump everything - even the C and C++ people are using C or C++, after all. Languages often trade run-time, compile-time and write-time performance. And you don't even have to look at languages and their implementations to see that - for example, compare the original Doom engine with Duke Nukem 3D. Doom's levels need significant compile-time - Duke's can be edited in real-time. Doom had better runtime performance, but it didn't matter by the time Duke launched - it was fast enough, and that's all that matters when you're dealing with performance on a desktop.

What about performance on a server? You might expect a much stronger focus on performance in server software. And indeed, for things like database engines, that's true. But at the same time, servers are flooded with software like PHP or Node.js. Much of what's happening in server-space shifted from "squeeze every ounce of performance from this central server node" to "just throw a hundred servers at the problem". Web servers were always designed for high concurrency (and decentralisation) - that's one big reason why HTTP and the web were designed to be state-less. Of course, not everyone got the memo, and it's handy to have some state - but it still makes decoupling state from a particular server much easier. PHP is not a powerful language. It's not particularly nice to work with. But it provided something people needed - simple templating for their web sites. It took quite a while for performance to become an important goal, and it was further "delayed" by sharding, caching, proxying etc. - which were very simple to do thanks to the *limitations* of PHP and HTTP.

But surely, you'll always write an OS in C/C++? Well, for the foreseeable future on the desktop, sure. But not because of raw performance - the trump card is compatibility. Many research OSes have cropped up over time that provide greater safety, security, reliability *and* performance (particularly in highly concurrent scenarios). A fully memory managed OS makes many of the costs of managed memory go away; better memory guarantees, type safety and runtime type information allow you to elude many runtime checks and costs with task switching etc. Immutability allows processes to share memory safely and easily, at very low cost (heck, many of Unix strengths and weaknesses come from how `fork` works). Doing compilation on the target computer means you can't spend so much time optimising, but it also means you are targeting a very specific configuration - so you can always use the best available CPU extensions, for example, without having to do any runtime checks. And of course, *safe* dynamic code can bring its own performance benefits too (my software 3D renderer in C# uses that heavily for shader code; funnily enough, thanks to all the high-level language features, it's much simpler, faster *and* more powerful than e.g. the Build engine that powers Duke Nukem 3D - at the cost of extra memory etc.).

We're doing engineering here (poor as it may be). There's trade-offs to be had. Unless squeezing every tiny bit of performance out of your language gives you the greatest possible benefit, you shouldn't be doing it. C wasn't getting faster to please C programmers; it was getting faster because there were people who used it to work on stuff that made things faster for *everyone else*. That's a lot of history that can be hard to beat, and would you really want to spend the next 50 years catching up with some low-level performance tweaks and fixing tiny incompatibilities when nobody would want to use your language in the first place because it doesn't provide them with any real benefit over C? :)
> 6 votes

# Answer
I reject the premise of "More powerful programming languages tend to have slower implementations."

"Power" is subjective. Is it faster? More robust? More exact? More efficient? More capable?

* A nuclear warhead is very powerful, but not very precise.
* An acupuncture needle is very precise, and can be very powerful, but it is only leveraging the underlying neural system.
* Lisp is very powerful, very precise, and yet, (some) people find it an awkward language.
* APL is very very powerful, precise, and succinct. But it requires a special keyboard (or mapping), and is sometimes labelled as too difficult to teach (though it's probably fairer to say it's not for everyone).
* Pascal isn't very powerful, but is fairly precise. It was designed as a teaching language, and also an experiment to prove that a one-pass compiler is practical. (Leave it to Microsoft to distribute a 3-pass compiler for a 1-pass language.)
* Python, Perl, Java, etc. These are easier to write in for most people, there are loads of libraries, tutorials, and online projects for examination. Many of these languages don't have "pointers" as such, but do have "references", which are more consistent with the language -- you don't have to bother with pointer arithmetic, wrap-around, and other implementation-specific details. Indeed, these were meant to be on most, if not all, hardware. They are an abstraction up from C and C compilers, making their programs more widely applicable without recompiling. But they lose some performance for this flexibility.
* Turing machines: the most powerful, and yet, when was the last time you wrote a program? Performance is awful, because, in all but pathological cases, there are better implementations.
* GOL (Game Of Life): since it's Turing complete, it's just as powerful, yet the performance is worse than a direct Turing machine implementation in the same context.
> 1 votes

# Answer
The phenomenon you describe as one language being more "powerful" than another one is what we call a "high-level" language vs. "low-level" languages.

But, what is the meaning of "level" in this context ? In other words, what they refer to being high/low level of ?

They refer to levels of abstraction. C/C++ is a language with low level (of abstraction). Python has a higher level (of abstraction).

The fact that high-level (of abstraction) languages are slower than low-level (of abstraction) ones is called abstraction penalty:

> High-level languages intend to provide features which standardize common tasks, permit rich debugging, and maintain architectural agnosticism; while low-level languages often produce more efficient code through optimization for a specific system architecture. Abstraction penalty is the cost that high-level programming techniques pay for being unable to optimize performance or use certain hardware because they don't take advantage of certain low-level architectural resources. High-level programming exhibits features like more generic data structures and operations, run-time interpretation, and intermediate code files; which often result in execution of far more operations than necessary, higher memory consumption, and larger binary program size. For this reason, code which needs to run particularly quickly and efficiently may require the use of a lower-level language, even if a higher-level language would make the coding easier. In many cases, critical portions of a program mostly in a high-level language can be hand-coded in assembly language, leading to a much faster, more efficient, or simply reliably functioning optimised program.

References:

Pankaj Surana, Meta-compilation of language abstractions
> 1 votes

---
Tags: programming-languages
---


# Question
Title: Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$
I would like some help for the computation theory.

There is a PDA that accepts the language $\\{0^n 1^a 2^b \mid n = a+b\\}$, so how can I express it into context free grammar? Any help would be appreciated!

That's what I was trying, I am not sure if it is correct or not

```
S -> 0SA | 0SB | empty
A -> 1
B -> 2

```

# Answer
> 1 votes
Unfortunately your grammar generates mixed $1$s and $2$s.

You can try something like this:

$S\rightarrow 0SB | S'$
$S' \rightarrow 0S'A | \varepsilon$
$A\rightarrow 1$
$B\rightarrow 2$

Notice that I don't know if in your problem $n$ can be $0$ or not (and similarly for $a$ and $b$), so maybe you have to fix something.

Anyway, here the idea is starting generating first some $0$s an all the $2$s, and then add the remaining $0$s and the $1$s: it is similar to the "standard" grammar used to generate $0^n 1^n$.

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


# Question
Title: How can I do a subtraction on unary numbers terminated in X on turing machine?
For example, if I have 11X1111X as input, the result should be X. For another example, input: 1111XX -\> 1111X. I am a complete beginner and all my tries so far failed to meet the expectation.

This was my latest try:

# Answer
> 1 votes
First of all, notice that if you have to compute $N-M$ you can subtract one from each operand and the result will not change (i.e. $N-M = (N-1) - (M-1)$.

Keeping that in mind, I would remove a 1 from each operand replacing it with another symbol Y just to avoid spaces on the tape, and repeat until either operand "runs out" of ones --that means that either $N$ or $M$ is now zero. When it happens, clean out the tape a little bit: the left operand is the result of the computation.

So, executing this algorithm in your examples: example 1

```
11X1111X input
Y1XY111X
YYXYY11X notice that the left operand is zero
  X      cleanup

```

example 2

```
1111XX input
Y111XX notice that the right operand is zero
1111X  cleanup

```

As you can see from the second example, if the first operand is bigger than the second you will have to revert the last substitution replacing a Y with a 1.

Another meaningful example:

```
1111111X1111X input
Y111111XY111X
YY11111XYY11X
YYY1111XYYY1X
YYYY111XYYYYX
YYYYY11XYYYYX notice that the right operand is zero
    111X      cleanup

```

As for the actual program, here is just a sketch, try to write it yourself:

* in q0 search for a 1 to replace. That means, skip all the Ys and continue moving right until you find a 1, then don't move and go to q1.
* in q1 replace the 1 with a Y, then move right and go in another state (q2) to reach the other operand.
* in q2, go right until you find an X (that means you have reach the second operand), then move right and go to q0 to remove a 1 from the second operand too.

This part will replace a 1 from both operands (if there are enough ones), the states of the machines are q0 -\> q1 -\> q2 -\> q0 -\> q1 -\> q2.

At this point the scanner is placed at the end of the input string, you realize it when you find an empty cell in q2, so;

* in q2, if you find an empty cell, move left and go to q3 (which will move the scanner at the beginning of the input).
* in q3 move left ignoring any character until you find an empty cell. That means you have reached the beginning of the string. Move right and go to q0.

This loop continues until either operand runs out of 1s. You realize it when you find an X in q0, so:

* in q0 if you find an X, move right and go to q4 that is the state that initializes the cleanup part
* in q4 move right ignoring any character until you find an empty cell, that means you have reached end of the input, move left and go to q5 to perform the cleanup phase.

Complete the program as an exercise: if you want you can edit this answer to add the sketch of the cleanup phase.

---
Tags: algorithms, turing-machines
---


# Question
Title: How to show a language is Partially Decidable?
I am trying to solve some questions on partial decidability of languages and I am getting confused in how to construct proper arguments through the idea of Universal Turing Machine.

I am not posting my questions here, so I would like some examples showing a certain language is partially decidable with a proof.

# Answer
> 1 votes
A language $L$ is partially decidable if there is a turing machine $M$ such that

* $M$ accepts on input $w$ if $w \in L$
* $M$ rejects or runs forever on input $w$ if $w \not\in L$.

For example, the language $L = \\{\mathrm{enc}(T) : \mathrm{enc}(T) \text{ is the encoding of a TM } T \text{ that halts on } \epsilon \\}$ is partially decidable, since one could define a TM $M$ as follows:

```
 def M(w):
    if w == enc(T):
        while True:
           simulate T(epsilon) for one step
           if T has halted:
               accept
    else:
        reject

```

one would then make a case distinction for every word $w$, so if

* $w \in L$, then $w = \mathrm{enc}(T)$ for a TM $T$ that halts on $\epsilon$. Therefore, if started with $w$, $M$ enters the `if`-part. Since $T$ accepts $\epsilon$ after a finite number of steps, the $T$ will halt eventually and $M$ will accept as well.
* $w \not\in L$. If $w$ is not a valid encoding of a TM, then $M$ will reject after the first step. On the other hand, if $w = \mathrm{enc}(T)$, then $T$ must be a TM that doesn't halt on $\epsilon$. In this case, it is easy to see that the while loop never stops and $M$ will run forever.

---
Tags: turing-machines, computability, proof-techniques, semi-decidability
---


# Question
Title: Question regarding the assumptions of the No-Free-Lunch-Theorem for Search
I am trying to understand the No-Free-Lunch-Theorem for search (can be found here: http://axon.cs.byu.edu/~martinez/classes/678/Papers/Wolpert\_NFLsearch.pdf) and have a question regarding the assumptions that were made by Wolpert et al. with respect to the "general nature" of a search algorithm.

In the paper, the following definitions were made:

* $\mathcal{X}$ is the (finite) population of solutions,
* $\mathcal{Y}$ is the (finite) evaluation space (e.g. a subset of $\mathbb{R}$),
* $f : \mathcal{X} \rightarrow \mathcal{Y}$ is a cost-function,
* $d\_m = \\{ d\_m(i) : 1 \leq i \leq m \\} = \\{ (d\_m^x(i), d\_m^y(i)) : 1 \leq i \leq m \\} \in \mathcal{D\_m}$ is the "history", i.e. the sequence of solution/cost-pairs $(x\_1,f(x\_1)),\dots,(x\_m,f(x\_m)) \in \mathcal{X} \times \mathcal{Y}$ that were found until time point $m$,
* $a : \cup\_{i \geq m} \mathcal{D}\_m \rightarrow \mathcal{X}$ is a decision function that yields the next solution dependent on the recent history and
* $\vec{c} \in \mathbb{N}^{\mathcal{Y}}$ is the histogram, which is the vector that stores the number of times every score was reached up until time $m$.

The work then shows that the equality $$ \sum\_{f} P(\vec{c} \mid f,m,a\_1) = \sum\_{f} P(\vec{c}\mid f,m,a\_2) $$ holds for all $m=1,2,\dots$ where $a\_1$ and $a\_2$ are arbitrary decision-functions and the sum spans over all possible cost-functions. The proof was done via induction on $m$, in which the equality $$ P(x \mid d\_m, f, m+1, a) = P(x \mid d\_m, a) $$ was neccessary for the induction step (page 6). As I understood it, this basically means: the choice of the next solution $x \in \mathcal{X}$ is only dependent on the previous history $d\_m$, since $x = a(d\_m)$, and therefore independent of the cost-function $f$.

I agree that this holds if based on the above definitions, but I don't really think that this is how most search algorithms work? For example, a simple hill-climbing-algorithm would select a set of neighbours for every solution, compare them, and would then select the best neighbour, dependent on how they score on the cost-function. Therefore, the choice of the successor $x$ would depend on $f$, and one would have something like $x = a(d\_m,f)$, i.e. the above part in the induction step wouldn't work.

So, my question basically is: am I missing something or is this work based on a wrong understanding of search algorithms?

# Answer
> 1 votes
I think that I was indeed misunderstanding something. Any search algorithm that wants to evaluate any point $x \in \mathcal{X}$ through $f$ would implicitly add $(x,f(x))$ to the histogram $d$. For example, one could design a hill-climbing algorithm in the following way:

* for a solution $x'$, visit all neighbours $x\_1,\dots,x\_n$
* afterwards, $(x',f(x')), (x\_1,f(x\_1)),\dots,(x\_n,f(x\_n))$ are all part of the histogram $d$
* choose the best neighbour from $x\_1,\dots,x\_n$ by computing $a(d) = \arg\min\_{x=x\_1,\dots,x\_n} f(x)$, which is independent of $f$ since $f(x\_1),\dots,f(x\_n)$ are already known
* repeat

---
Tags: correctness-proof, search
---


# Question
Title: 4 Vertex Cover Problem is not NP Complete why?
With Given Graph $G$ why finding that $G$ has a vertex cover of at most $4$ is in $P$ and Not in NP Complete. it means there us poly-time algorithm for this problem !!?

# Answer
> 0 votes
If your graph has $n$ vertices, there are $O(n^4)$ possible subsets of $4$ vertices. Given one such subset, it is easy to check if it is a cover in $O(n^2)$ operations, by inspecting every edge and verifying whether it has an endpoint in the given subset.

Thus, in $O(n^6)$ operations we can check all possibilities.

---
Tags: algorithms, complexity-theory, graphs, computability, np-complete
---


# Question
Title: Find The "Best" Permutation of Inputs to Maximize Sum of Functions (or approximate "best")
## The Problem (in words)

I want to sort $N$ items where the value of item $i$ at position $p$ is given by the function $f\_i(p)$. The "best" order for these items is the one that maximizes the total value of my items but I am willing to accept a "good" order if it means finding it quickly.

## The Problem (in maths)

Given $N$ monotonically decreasing functions $f\_i$(x) where $1 \<= i, x \<= N$ and a set $S = \\{1, 2, 3, ..., N\\}$

Find $\alpha$, a permutation of $S$ which maximizes the objective function $g(\alpha) = \sum\_{i=1}^{N} f\_i(\alpha(i))$

In the event that this is a hard (e.g. NP-Complete) problem, I would rather have an approximation algorithm which returns a permutation that gives some local maxima of $g$ with provable guarantees on the distance to the optimal one.

## My Thoughts

I am not very familiar with optimization problems but this feels like one that should be well known. I feel that if I knew the name of it I would have been able to search it on my own.

I am able to put more constraints on $f\_i$ if needed but I would prefer to allow it to be any monotonically decreasing function.

I cannot brute force this as the values of $N$ I work with lead to far too many permutations.

My initial thought was to use a greedy algorithm which chooses the highest valued remaining item starting with position 1 and iterating until position N. I know this will not produce the best result but it is possible it produces a "good enough" result. I am not comfortable with using this greedy algorithm unless I have a proof of how effective it is.

# Answer
One approach is to view this as an instance of the assignment problem: you have a bipartite graph, with items on the left and positions on the right, and $f\_i(p)$ tells you the value of matching item $i$ to position $p$, so draw an edge $i \to p$ with weight $f\_i(p)$, and then find the maximum-weight bipartite matching. This will give an optimal solution. It also demonstrates that the problem can be solved in polynomial time, i.e., it is not NP-hard. The running time will be $O(n^3)$, which might be reasonable if $n$ is not too large but might be too expensive if $n$ is very large.

It might be possible to find some other algorithm that is more efficient (i.e., has faster runtime), by taking advantage of the fact that each $f\_i$ is monotonically decreasing.
> 2 votes

---
Tags: optimization, approximation, discrete-mathematics, permutations
---


# Question
Title: Are there undecidable languages which are well defined?
It would be a mess if the answer had to be NO after all these speculations and theorems about these languages but..

I am not conviced liar paradox is well defined. And Godël himself said his theorem is just an exhibit of a liar paradox.

I am not conviced halting problem is well defined.

I am pretty conviced that if you formalize the statement 'Does this man both having only 2 ears and 3 ears went to his house on monday ?' you get something that you can not prove true nor false, just because it would suppose to define something in the proof which can not be defined.

I am not conviced that any 'undecidable' Godel statement is undecidable in an other meaning than this.

I am pretty conviced than you can not correctly define any consistent theory that would not be decidable by a turing machine. I think this is the profond meaning of Church Thesis.

I am pretty conviced that if you take a statement which would be undecidable even for a turing machine, if you add this statement as axiom to any turing complete theory, you get something inconsistent because I am pretty conviced than you can proof both the statement and it's unprovability.

I am not sure that the separation of syntax and semantic is relevant anywhere in theoretical computer science, yes you can specify what you are doing and it can help in some application, but I am pretty conviced you do not need this do define mathematics.

# Answer
The halting problem really is well-defined. Allow me to state it in terms of languages as you'd want.

Recall the definition of a decidable language. A language $L$ is decidable iff there exists a Turing machine $T$ such that for all inputs it can decide whether the input word is part of the language in a finite number of steps.

Furthermore, let us remind ourselves that Turing machines are universal, and can simulate each other. That is we can build a Turing machine $U$ that given some encoding of another Turing machine $T$ and input $x$ when run $U$ will have the same outcome (yes/no/does not halt) as $T$ would on $X$. They are also countable, so for each Turing machine there is an encoding and vice versa.

Now let $L$ be the language of the encodings of Turing machines that halt when they receive their own encoding as input. Assume there exists a Turing machine $D$ that correctly decides this language. Construct $H$ to run $D$ on its input (similar to $U$), but unlike $U$ if $D$ returns yes it goes into an infinite loop and otherwise halts with some value.

Now asking if $H \in L$ gives us a contradiction, so our assumptions are wrong . But we got $H$ from $D$ in simple finite computable steps. Thus it must be our assumption that $D$ exists is wrong. But if that assumption does not hold we must conclude that $L$ is not decidable.
> 2 votes

# Answer
Here's a repackaging of the halting problem you may find easier to think about:

Consider the **Diophantine solution problem**: which Diophantine equations (= polynomials with integer coefficients set equal to zero) have solutions? This is about as concrete as things get, yet by the MRDP theorem this is basically the halting problem in disguise. Specifically, there is a computable function $f$ from (indices for) Turing machines to (codes for) Diophantine equations such that $f(e)$ has a zero iff $e$ halts on input $0$, and so a fortiori there is no algorithm for determining whether a given Diophantine equation has a solution.

And many more examples of concrete non-logic-based conditions yielding non-computable sets can be found here. In particular, this answer specifies a *single Diophantine equation* whose instances with respect to one variable (e.g. take a particular variable and think about plugging in specific natural numbers for it) yield non-computability.

---

I suspect your confusions stem from taking a "quick summary" too seriously. E.g. when you write

> Godël himself said his theorem is just an exhibit of a liar paradox,

you're treating a vague intuition as a rigorous result, and it's really not. The incompleteness theorem is *motivated by* the Liar Paradox, but that doesn't mean that it *is* the Liar Paradox, and this will become clear if you examine in detail a proof of the theorem. (I **strongly** recommend a modern presentation, rather than Godel's original argument, since the details have been substantially cleared up over the last several decades; in math you usually *don't* want to go back to the original source.)
> 0 votes

---
Tags: undecidability
---


# Question
Title: If L is context free and R is regular then R – L must be context free?
Hi I am wondering if L is a CFL and R is RL then would the difference R - L be a context free language?

The difference might be the CF part of the language left then it would be, but I'm not sure how I could go about proving this without giving an example

# Answer
> 1 votes
Context-free languages are not closed under complement. This is a fairly well-known result.

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


# Question
Title: minimum number of points a convex hull must have
Quick question:

Say for example there are 10 colinear points. my question is does a convex hull *have* to be a convex polygon? or can it be a line as well according to the formal definition of the convex hull?

Thanks in advance.

# Answer
The convex hull of 10 collinear points is the line segment between the two extreme points.

No, a convex hull does not have to be convex polygon. A convex hull can be a point, a line segment, a ray, a line, a convex polygon, a circular sector, a half plane, a cubic, etc. .

A definition in math, such as the definition of convex hull, is the strictest kind of definition. It means exactly what it says. No more, no less.
> 3 votes

---
Tags: data-structures, computational-geometry, convex-hull
---


# Question
Title: Closure properties of Alternating Circuit 1 level
Recall that $\mathsf{AC^1}$ is the class of circuits with unbounded fan-in, polynomial size, and logarithmic depth.

Is this class closed under Kleene star? I thought it would be simple since it is easy to check every subword (using a polynomial number of gates), but the part where I have to check every partition makes the circuit linear in depth.

# Answer
Denote your language by $L$. Let the input be $x\_1,\ldots,x\_n$. Let $f(i,j,\ell)$ be true if $x\_1,\ldots,x\_j \in L^\ell$. The output will be $$ \bigvee\_{\ell=1}^n f(1,n,\ell). $$ When $\ell = 1$, there is an $\mathsf{AC^1}$ circuits for $f(i,j,\ell)$. When $\ell \> 1$, we use the formula $$ f(i,j,\ell) = \bigvee\_{k=i}^{j-1} (f(i,k,\lfloor \ell/2 \rfloor) \land f(k+1,j,\lceil\ell/2\rceil)). $$ The resulting circuit is still $\mathsf{AC^1}$, since there are only $O(\log n)$ levels of recursion.

A different way of looking at this construction is to notice that for inputs of length $L$, we can replace $L^\*$ with $L \cup \cdots \cup L^n$; and that $L^m$ can be computed in $O(\log m)$ steps using repeated squaring.
> 1 votes

---
Tags: complexity-theory, circuits, kleene-star
---


title: Language Containment of Automata

text:
# Question
Title: Language Containment of Automata
If we are given an NFA and a DFA, can we determine if there exists a string accepted by the NFA and rejected by the DFA and vice-versa. What complexity class would these problems fall into?

# Answer
> 3 votes
I will guide you through it, giving you the most important ideas. Yet, I will leave the details for you, many details actually. For two languages $A, B$, it holds that $A\subseteq B$ iff $A\cap\overline{B} = \emptyset$. This is an easy exercise and I leave it to you. Now given two automata $C\_1$ and $C\_2$, we can check whether $L(C\_1)\subseteq L(C\_2)$ by checking the emptiness of $L(C\_1)\cap \overline{L(C\_2)}$. In general, constructing an automaton for the intersection of two automata is easy, regardless of whether the automata are DFAs or NFAs (by easy I mean it can be done in time polynomial in the two automata): indeed, one can show that the product construction of automata can be generalised to NFAs. So, given two NFAs, one can build an NFA over their product to recognise their intersection. Then, to check whether the product automaton is empty, we can simply check if there is a path from an initial state to an accepting state in the product - which can be done in time polynomial in the size of the product automaton (polynomial in the size of the automata that we're intersecting). So, to solve the above problem, one can do the following.

Given automata $C\_1$ and $C\_2$, construct an automaton for $D = \overline{L(C\_2)}$, then construct a product automaton $E$ for $L(C\_1)\cap L(D)$, and finally check whether $L(E)$ is empty - which takes time polynomial in $|E| = |C\_1|\cdot |D|$. So the complexity depends on the size of $C\_1$, and on the size of $D$ which recognizes $\overline{L(C\_2)}$. So $|E|$ is polynomial in the sizes of $C\_1$ and $C\_2$ iff $|D|$ is polynomial in them. To sum up:

* If $C\_1$ is an NFA and $C\_2$ is a DFA, then $D$ is obtained from $C\_2$ by flipping accepting and rejecting states. So $|D| = |C\_2|$, and thus solving the problem takes time polynomial in $|C\_1|\cdot |C\_2|$. Hence, the problem in this case is in P.
* If $C\_1$ is a DFA and $C\_2$ is an NFA, then $D$ is obtained from $C\_2$ by applying the subset construction. So $|D| = 2^{|C\_2|}$, and thus solving the problem takes time polynomial in $|C\_1|\cdot 2^{|C\_2|}$, which is exponential. Hence, the problem in this case is in EXPTIME. In fact, it can be shown that the problem is in PSPACE. Idea: we do not need to construct the whole product automaton, and then find a path in it. Instead, we can find this path nondeterministically on the fly in polynomial space (use the fact that PSPACE = NPSPACE, and the fact that given a state in the product, you can compute its successor states if you have the description of $C\_1$, and $C\_2$. Once you guess a successor state, you can remove the current state. This way, you do not need to construct the whole product, you only store the current state in the guessed path). I left out some important small details to you. Also, you can show that the problem in this case is PSPACE-hard by reducing the NFA-universality problem to it. Indeed, given an NFA $A$, a reduction outputs $C\_1, C\_2$, where $C\_1$ is a DFA that accepts all words, and $C\_2 = A$. Clearly, $L(A) = \Sigma^\*$ iff $L(C\_1)\subseteq L(C\_2) = L(A)$. Thus, PSPACE-hardness follows.

---
Tags: complexity-theory, finite-automata, np
---


# Question
Title: Comparing two algorithms for all-pairs shortest paths
I read in my notes:

> If we use Dijkstra $|V|$ times ($|V|$ number of vertices) for finding **all-pairs shortest paths** in graph $G$, we get time complexity for Dijkstra algorithm as $O(VE+ V^2 \log V)$, and if we run Bellman–Ford algorithm $|V|$ times, we get time $O(V^2E)$.

The above details are not important.

I read too, that Dijkstra's algorithm works better for sparse graph, that is, $O(VE+ V^2 \log V)$ is better than $O(V^2E)$ asymptotically for sparse graphs.

I think sparse graphs are graphs satisfying $ |E| = O(V)$ or $E=o(V^2/\log V)$. In fact, I have two misunderstandings:

1. Which one is more common as the definition of a sparse graph?
2. According to 1, how we can intuitively understand that $O(VE+ V^2 \log V)$ is better asymptotically than $O(V^2E)$? At least I think the reverse is true.

# Answer
> 2 votes
There is no standard definition for sparse graphs. Some common definition include graphs in which $E = o(V^2)$, $E=O(V^{2-\epsilon})$, $E = O(V^{1+\epsilon})$, $E=O(V^{1+o(1)})$, $E = O(V\log^C V)$, and $E = O(V)$.

In most situations, it is safe to assume that the graph is connected, and so $E \geq V-1$. In such cases, $VE + V^2\log V = O(V^2 E)$, and so an upper bound on the running time of the form $O(VE + V^2\log V)$ is better than an upper bound of the form $O(V^2 E)$: indeed, the former implies the latter.

---
Tags: algorithms, graphs, time-complexity, data-structures, asymptotics
---


# Question
Title: PCP when upper and lower words have different length
The Post correspondence problem (PCP) asks, given two sets of words $a\_1,\ldots,a\_n$ and $b\_1,\ldots,b\_m$ over the same alphabet, whether there are indices $i\_1,\ldots,i\_s \in \\{1,\ldots,n\\}$ and $j\_1,\ldots,j\_t \in \\{1,\ldots,m\\}$ such that $$ a\_{i\_1} \ldots a\_{i\_s} = b\_{j\_1} \ldots b\_{j\_t}. $$ It is well-known that PCP is undecidable.

What happens if we restrict $s \neq t$? Does the problem become any easier?

# Answer
The problem doesn't become any easier.

Suppose we are given an instance $a\_1,\ldots,a\_n,b\_1,\ldots,b\_m$ of PCP. Let $\sigma$ be a new symbol. Add to the first list the words $a'\_1 = \sigma a\_1,\ldots,a'\_n = \sigma a\_n$, and to the second list the word $b'\_0 = \sigma$.

If the new PCP instance has a solution, then we can obtain a solution of the original PCP instance by removing all occurrences of $\sigma$. Now suppose that the original PCP instance has a solution $$ a\_{i\_1} \ldots a\_{i\_s} = b\_{j\_1} \ldots b\_{j\_t}. $$ If $s \neq t$ then this is a solution of the new PCP instance in which $s \neq t$. If $s = t$, then consider the following solution instead: $$ a'\_{i\_1} \ldots a\_{i\_s} = b'\_0 b\_{j\_1} \ldots b\_{j\_t}. $$
> 0 votes

---
Tags: computability, decision-problem
---


title: How to calculate O-Notation?

text:
# Question
Title: How to calculate O-Notation?
I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; What I would like to ask, if there is a certain way to find out O-Notation? Actually I know that the purpose of O-Notation, it helps us to estimate the effciency of algorithm. But in a specific questions like O(2^n) * O(n^10) I assumed that O(2^n * n^10) as in the worst case but learned that I was false, it should be 2^n and I don't know why? Shouldn't we think that which term would go faster to eternity, and in this case I thought that when I multiply both then it can go faster than 2^n, can't it? Could anyone explain please ? Just short and with beginner sight:)

# Answer
> 1 votes
We can show that $O(2^n\cdot n^{10}) \not\subset O(2^n)$:

As $2^n\cdot n^{10} \in O(2^n\cdot n^{10})$, then, if also holds $2^n\cdot n^{10} \in O(2^n)$ then we will have $2^n\cdot n^{10} \leqslant C 2^n$, which gives false $n^{10} \leqslant C$.

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


# Question
Title: How to find the alphabetically min and max of substrings that begin with [a, b, c, d, e] and end with [h, i, j, k, l, n]
I was asked this question today:

given a very long string x, which contains only lower case alphabets. A valid substring can only started with \[a, b, c, d, e\] and ends with \[h, i, j, k, l, n\]

IF we sort the valid substrings alphabetically, what will be the first one and what will be the last one?

If we do need to sort all the substrings, then we might need a suffix tree or suffix array. However, here we do not need to sort --- we don't care all the substrings except the first and last one. So I am wondering if there is any more efficient solution than using suffix array.

Thanks

# Answer
> 1 votes
Find the last occurence of any h, i, j, k, l, n. If none is found, there is no solution. If the last one is found at position r, then the string we are looking for must start at position before r.

Then you start from the left looking for the first letter among a, b, c, d, e. If you don't find one before position r then there is no solution. Otherwise call this index l; the first string in the alphabet *might* start at index l.

Look further for more characters starting with a to e. If you find one at position l', you then find the first difference between the string starting at l and l', up to and including position r. If there is a different character, and the first character in the string starting at l' is earlier in the alphabet, replace l with l'.

Finally, the first string in the alphabet is the one starting at position l, and up to and including the first letter in 'h' to 'n'.

PS Re-reading this after more than a year there may be some more or less subtle bugs in this code, but it is roughly right.

---
Tags: search-algorithms, substrings, suffix-trees
---


# Question
Title: Is there any reason why the modulo operator is denoted as %?
I would like to know if there is any reason why many programming languages use the notation `%` for the modulo operator?

It is used in the most "famous" languages:

* C
* C++
* C#
* Go
* Java
* Julia
* Lua
* Perl
* Python

# Answer
The earliest known use of `%` for modulo was in B, which was the progenitor of C, which was the ancestor (or at least godparent) of most languages that do the same, hence the operator's ubiquity.

Why did Thompson and Richie pick `%`? It had to be a printable ASCII character that wouldn't conflict with B's other features. `%` was available, and it resembles the `/` division operator, making it the obvious choice.

p.s. the creator of ASCII invented `\` to represent "reverse division", so it wasn't a candidate for modulo.
> 45 votes

# Answer
This is very likely a historical development. Looking at this table, we see that **C** was likely the first language to use `%` for modulo. Its predecesor BCPL used `rem`, and older languages such as Fortran, Algol, Lisp, and Cobol did not use `%`. But that's just my uninformed guess.
> 13 votes

# Answer
> I would like to know if there is any reason why many programming languages use the notation % for the modulo operator?

I would strongly suspect it is because both Unix and Windows (the two operating system families that have survived to the present day), chose C as their main programming language. The result is most of the programming languages we use today, were designed in environments where C and/or C++ were the dominant "systems" programming language.

People designing a new language will undoubtedly have aspects that they wish to change from previous languages, but there will also be aspects that they think are fine the way they are or at least aspects they can't think of a better solution for. Development of mainstream programming languages has been more evolutionary than revolutionary.

The result has been that most successful programming languages over the past few decades have been directly or indirectly influenced by C. Lets look at the languages on your list in chronological order and see what environments they were developed in and/or what languages were used to develop them.

* C++: designed by Bjarne Stroustrup while working on Unix at AT&T in 1979 as an object orientated extension of C.
* Perl: Created by Larry Wall in 1987 while working at Unisys. Perl is written in C and it's clear from the initial announcement newsgroup post that perl was designed to be used on a Unix system.
* Python: Created by Guido van Rossum around 1989 while working at a university. Again Python is written in C and was written with Unix, Windows, Mac and an experimental OS the university was working on in mind.
* Lua: Created at a Brazilian University in 1993. It was written in C, though there were certainly many influences from other languages. It's probably the least C like of the languages here.
* Java: designed by Sun Microsystems (a Unix vendor) in 1995. Largely implemented in C++ and borrows much of it's basic syntax from there.
* C#: designed by Microsoft in 2000 as a substitute for Java after they fell out with Sun over MS-specific extensions to Java.
* GO: Designed at Google in 2007 in reaction to problems Google engineers percived in C, C++ and Python, borrows most of it's syntax from C.
* Julia: Developed in 2009, targetting Linux, Windows and Macos, appears that the non-julia parts are written in C.
> 2 votes

---
Tags: programming-languages, notation, history
---


# Question
Title: An equivalent of $\neg ((a \wedge b) \Leftrightarrow c)$ based on a specific requirement
I am solving a problem that is asking to provide an equivalent for $\neg ((a \wedge b) \Leftrightarrow c)$ and the equivalent shouldn't contain $\wedge$ (and), $\Rightarrow$ (implication) or $\Leftrightarrow$ (iff). What I have worked out is:

$\neg(\neg((\neg a \vee \neg b) \vee \neg c) \vee \neg(\neg(\neg a \vee \neg b) \vee c))$

I wonder based on the requirement stated above, is there a shorter equivalent for my answer?

**Update**

$\oplus$ is not allowed in the requirement either.

# Answer
Outgoing from requirements can you use $\oplus$? if yes, then, as we know, that $\neg(a\Leftrightarrow b) = a \oplus b$, then we can obtain $$\neg ((a \wedge b) \Leftrightarrow c) = \neg (\neg a \lor\neg b) \oplus c$$

**Update**.

Accordingly to your update I wrote my one: not shorter, slightly different, but logically equivalent yours one $$\neg \big\[(a \wedge b) \Leftrightarrow c\big\] = \\ =\neg \big\[\big((a \wedge b) \Rightarrow c \big) \land \big(c \Rightarrow (a \wedge b)\big) \big\]=\\ =\neg \big\[ \big(\neg (a \wedge b) \lor c \big) \land \big( \neg c \lor (a \wedge b) \big) \big\]=\\ =\neg \big\[ \big(\neg a \lor\neg b \lor c \big) \land \big(\neg c \lor \neg(\neg a \lor\neg b) \big) \big\]=\\ = \neg\big(\neg a \lor\neg b \lor c \big) \lor \neg\big( \neg c \lor \neg(\neg a \lor\neg b) \big) $$
> 3 votes

---
Tags: logic
---


title: Usefulness of Differential Geometry

text:
# Question
Title: Usefulness of Differential Geometry
I recently came across these books:

Their subject matter really intrigues me, as I really enjoy topology/geometry/analysis, but had not planned to pursue them since I also want to work in an area with very concrete application. However, I am skeptical. At one point I thought topological data analysis (TDA) was the perfect marriage of my interests, but I have found very little evidence of that field actually being used in computer science, much less in industrial or otherwise more 'practical' settings. It seems like TDA makes mathematicians feel more relevant to the data science world, but I'm not convinced that it makes them so (feel free to contradict me if you think I'm wrong on this point, but note that I want a concrete use case, not an abstract argument about its relevance). I have similar stories about coding theory, certain aspects of set theory, etcetera. They may have theoretical relevance, but is there any situation where, in the process of developing software, one might need to consult theses fields? I don't know of any.

So now my question: is there any practical field of computer science that makes advanced use of differential geometry? Medical imaging, other imaging, computer graphics, virtual reality, and some other fields come to mind as potential application areas. In my (admittedly limited) experience, however, these areas seem to use basic 3D geometry, numerical linear algebra, and sometimes numerical analysis of PDEs. Those are all very nice topics, but they do not require anything as abstract as differential geometry.

Thanks in advance.

# Answer
> 0 votes
I mainly see differential geometry applied to computer science in the following applied subfields:

* Computer Graphics / Geometry processing
* Machine Learning / Signal Processing

For Computer Graphics / Geometry processing, recommend looking for:

For Machine Learning /Signal Processing recommend looking for:

Also check this answer in Math exchange, and this conference Differential Geometry meets Deep Learning

Btw the Functional Differential Geometry is a great book.

# Answer
> 1 votes
If you found *Structure and Interpretation of Computer Programs* interesting, you might like Functional Differential Geometry (It's from the same authors) .

> Differential geometry is deceptively simple. It is surprisingly easy to get the right answer with unclear and informal symbol manipulation. To address this problem we use computer programs to communicate a precise understanding of the computations in differential geometry. Expressing the methods of differential geometry in a computer language forces them to be unambiguous and computationally effective. The task of formulating a method as a computer-executable program and debugging that program is a powerful exercise in the learning process. Also, once formalized procedurally, a mathematical idea becomes a tool that can be used directly to compute results.

Taken from Sussman, Wisdom: *Functional Differential Geometry*

# Answer
> 0 votes
Nowadays, every field which has the name "differential" in it, is somehow applied in neural networks. For differential geometry for example you can think about differential rendering in computer graphics.

At the moment I am working with the paper "A Differential Theory of Radiative Transfer" by Zhang et al.

---
Tags: computational-geometry, mathematical-programming, mathematical-foundations, mathematical-software
---


# Question
Title: Is there a pushdown automaton for $\Sigma^* \setminus \{ a^n b^n c^n \mid n \ge 0\}$?
According to this statement:

> Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular language and its complement are a pair of complementary context-free languages.

$\\{a^n b^n c^n \mid n\ge0\\}$ is not deterministic context-free language so is $\Sigma^\* \setminus \\{ a^n b^n c^n \mid n \ge 0\\}$ a deterministic context-free language? If it is, how does it look like?

($\Sigma^\*$ means every possible string that can be generated with $\\{a,b,c\\}$.)

# Answer
The complement of a deterministic context-free language is also deterministic context-free. Since $\\{a^nb^nc^n \mid n \geq 0\\}$ is not context-free, its complement cannot be deterministic context-free. However, the complement *is* context-free, since it can be written as follows: $$ \overline{a^\*b^\*c^\*} \cup \\{a^{n+k} b^n c^m, a^n b^{n+k} c^m, a^{n+k} b^m c^n, a^n b^m c^{n+k}, a^m b^{n+k} c^n, a^m b^n c^{n+k} \mid n,m \ge 0, k \ge 1 \\} $$
> 3 votes

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


title: shortest path in color-weighted graphs

text:
# Question
Title: shortest path in color-weighted graphs
I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum of the weights of the colors used. If we have for example a path A-\>B-\>C where A and C are red colored and B is blue colored, its length should count the weight of red only once (and the weight of the blue node)! I'm struggling to find an (efficient) algorithm that can do this. Dijkstra's algorithm or any greedy algorithm cannot work, because they require that a local optimum must be also a global optimum. Here, this is not the case because the weight of a vertex depends on the path to it. You could add vertecies for each combination of colors but this would add exponantially many vertecies.

It would be enough for me to find such an algorithm for DAGs.

Thank you very much for your help!

# Answer
This problem seems to be NP-hard. A reduction from 3-SAT is left as an exercise, but here is a hint. The empty nodes are free, and then create a color for each literal and its negation. The cost is 1 for each. You can then visit a "clause" for free if and only if one of its literals is selected. Now, the cheapest s-t-path costs $n$ if and only if the formula is satisfiable.
> 2 votes

---
Tags: graphs, shortest-path, weighted-graphs, colorings, dijkstras-algorithm
---


# Question
Title: Finding pair of sum in sorted array in time complexity less than $O(n)$
In a sorted array, I am trying to find just one pair that sum up to a certain value. I was wondering if anyone could help me improve my code in performance or memory. I know the code which is $O(n)$. If there are other method for finding pairs the sum up to a certain value that is much more efficient.

I was asked this in an interview recently and interviewer told me that there exists a solution with $O(\log n)$ time complexity. Any ideas are appreciated.

# Answer
> 2 votes
Your interviewer is wrong.

Suppose that you had an algorithm which gets as input a sorted integer array $A\_1,\ldots,A\_n$, outputs Yes iff $A\_i + A\_j = 0$ for some $i \neq j$, and always accesses at most $n-1$ inputs.

Suppose first that $n = 2m$ is even, and consider the following sorted integer array $B$: $$ -2m, -2(m-1), \ldots, -4, -2, 1, 3, \ldots, 2(m-1)-1, 2m-1. $$ This array contains no solution to $B\_i + B\_j = 0$. For any index $i$, we can create a sorted integer array $B^{(k)}$, differing only in the $k$'th entry, which does have a solution to $B^{(k)}\_i + B^{(k)}\_j = 0$.

Now run the given algorithm. Whenever it tries to access a position $A\_i$, answer the value $B\_i$. By assumption, the array terminates without querying some position, say $A\_k$. Therefore the algorithm behaves the same when given as input the arrays $B$ and $B^{(k)}$, although the answer is No for the first one and Yes for the second one.

When $n=2m+1$ is odd, a similar argument works with the following sorted integer array: $$ -2m, -2(m-1), \ldots, -4, -2, 1, 3, \ldots, 2(m-1)-1, 2m-1, 2m+1. $$

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


# Question
Title: Operating System - CPU scheduling Decisions
I understand that CPU scheduling takes place on 4 circumstances listed below:

1. When the process changes state from Running to Ready
2. Changes state from Running to Waiting
3. Changes state from Waiting to Ready
4. Process Terminates

However, i notice that the CPU scheduling does not take place when Ready to running. Why is this so?

# Answer
> 2 votes
The only way that a process can go from "ready" to "running" is if the scheduler just scheduled it. Running the scheduler as soon as the process started running would mean that you'd actually be running the scheduler the whole time.

# Answer
> 2 votes
When a process moves from **running** to **ready**, to **waiting**, or to **finished**, it just lost the use of the CPU, a CPU is free and the scheduler has to select a new process to run.

When the scheduler selects the next process to run, it picks it from the ones in **ready** to move to **running**. It is *part* of the scheduling process, it doesn't trigger it's running.

# Answer
> 1 votes
If a process is "*ready*", that implies that it is ready to get scheduled (and thus executed or "*run*"). And only if a process is "*ready*", it gets scheduled.

And in what ever order the processes get scheduled, they are supposed to "*run*" (get executed by the CPU) in that order itself. That is the fundamental notion of scheduling processes which are "*ready*" to be "*run*" on the CPU.

I suggest, you go through, Operating System Concepts, Galvin et al. ( Ch. 5 - CPU scheduling -\> 5.1.3 Preemptive Scheduling).

# Answer
> 0 votes
when you say a process is **ready** it means that it is in prime condition to be scheduled by the processor and go into the running state.

once it goes into the **running state** it can either go to the wait/sleep/termination,and from the wait/sleep it can go to the ready state again or as the first condition displays jump directly from the running to ready queue in case there is a FIFO or a rate monotonic scheduling.

so yes...it all depends upon the scheduler scheme...but as far as your question goes as to why there is no scheduling from the **Ready-\>Running** states..the scheduler assembles the process queue as per a scheduling algorithm and then the processor is free to execute them from the queue as the come one by one i.e like the basic of how it works.

# Answer
> 0 votes
A CPU does Scheduling decisions only when it doesn't know which the next process is. If the scheduler decides that process `P` which is currently in Ready State should start running on CPU, then why will the CPU further do the Scheduling?

Even more, When an process `P` goes from Ready to Running, the CPU now indulges in executing the dispatcher module (A module which is part of OS that gives control of the CPU to the process selected by the processor). The CPU should start context switching since it knows which the next process is. So, it doesn't waste it's time doing CPU Scheduling.

PS: Same is the case with "Waiting to Running".

TLDR: You're asking "*Why the CPU is not solving the problem?*" when in fact the CPU already has a valid solution (i.e start executing the process decided by the scheduler).

---
Tags: operating-systems, process-scheduling, cpu
---


title: A basic question about predicate logic

text:
# Question
Title: A basic question about predicate logic
Suppose we have a statement: "Tom has a car" and we have an auxiliary clause that is

`has(x, y): x has y` then to write the statement in logic I am guessing the following ones:

$\exists$y has(Tom,y)

or

has(Tom,car)

The reason I am not sure which to select is I don't know whether or not "car" is a specific constant similar to Tom?

# Answer
> 2 votes
There is no universal answer. It depends on how you choose to model the universe of discourse you've been assigned to model.

We'd normally expect there to be multiple cars that appear as distinct individuals in the model, and we expect the predicate *has* to be the relationship that expresses which individual owns which individual object, i.e. between individual persons and individual cars. In that case, if *car* is a constant, it must denote a particular car, so you'd need other constants, for instance, *car2*, *car3*, etcetera, to denote other cars. It's awkward, but it can be done.

So it is valid, but very impractical. In practice, we usually see a predicate *is\_car(x)*, as Yuval Filmus suggests, and a couple of individuals for which that predicate holds that stand for the individual cars that exist in the universe of discourse being modelled.

*Tom* can be a constant representing a particular person, and we can use other constants such as *Dick* and *Harry* to represent other persons. Courses in logic tend to do this because they are proper names and they use sentences such as *Tom has a car* which imply that there is, indeed, exactly one Tom in the universe of discourse, so you can do this.

Once again: this is valid, and probably what your professor wants you to do, but it is highly impractical.

In practical applications of logic, e.g. when designing a relational database, we can't usually assume that names such as *Tom* uniquely identify a person, so we model names not as constants, but as predicates.

For instance, we may use a predicate *has\_first\_name(x,y)*, and the statement *Tom has a car* can then be expressed as

$\exists! x: \mbox{has\_first\_name}(x,\mbox{"Tom"}) \\ \wedge \\ \exists x: \mbox{has\_first\_name}(x,\mbox{"Tom"}) \wedge \exists y: \mbox{is\_car}(y) \wedge \mbox{has}(x,y)$

PS: Mars points out a more serious issue with using constants for cars: they always refer to a particular car, and *Tom has a car* doesn't - you could only express it by a statement that lists every individual car, like this: $\mbox{has}(\mbox{Tom},\mbox{car}) \vee \mbox{has}(\mbox{Tom},\mbox{car2}) \vee \ldots$.

# Answer
> 2 votes
I agree with reinierpost's answer and with Yuval Filmus's and lemontree's comments. Here are some additional points.

In English "a car" in "Tom has a car" usually means that there is some car that Tom has. "a car" is not a name of a specific car. That is, it is not a constant. You could treat "car" as a name of an object, and give the answer as "has(Tom,car)", but that would not be a correct representation of the English sentence you provided. (If the phrase was "the car", it would be possible to treat that as a constant, although the semantics of this phrase is actually more complex.)

If instead you just write "$\exists y$ has(Tom, y)", that just means that Tom has something. It says nothing about cars. So you really do need an "is\_car" predicate, as Yuval Filmus and lemontree suggested, to capture the meaning of the English sentence containing "a car".

In the preceding comments, I assumed that your domain contains at least persons and cars, and that "Tom" is the name of a person.

However, if you specified that the domain consisted *only* of cars, then "$\exists y$ has(Tom, y)" would capture the meaning of "Tom has a car": The formal representation would still only say that Tom has something, but since the only things are cars, that means that Tom has a car. Note though that in this case, since all things are cars, "Tom" would be the name of a car. So "$\exists y$ has(Tom, y)" would say, of a car named "Tom", that it owns a car. (That wouldn't usually make sense to us, because in our society we usually assume that cars can't own cars, but in this representation we would assume that they can. I suppose that might make sense in the world of the *Cars* animated movies, but I haven't seen them, so I don't know whether the characters in the films ever engage in automotive slavery.)

---
Tags: logic
---


# Question
Title: How does Lamport imply anomalous behavior is impossible given these constraints?
Lamport's paper: Time, Clocks, and the ordering of Events in a Distributed System

Anomalous behavior occurs because Lamport's logical clocks are not enough to guarantee that the total ordering of events derived from the unique partial ordering and a non-unique total ordering is not enough to guarantee that the ordering is correct with respect to physical time.

He gives two conditions PC1 and PC2:

PC1: There exists a constant $ \kappa $ \<\< 1 such that for all i:

$ |\frac{dC\_{i}}{dt} - 1| \< \kappa $

PC2: For all i, j:

$ |C\_{i}(t) - C\_{j}(t)| \< \epsilon $

PC1 says that individual clock drift in the system must be less than some constant $ \kappa $. PC2 says that clocks must be synchronized so that the difference in time between any 2 clocks does not exceed $ \epsilon $.

**This is what I do not understand.** He says that anomalous behavior is impossible if this proposition holds, deduced from PC2.

proposition: PC2 implies $|C\_{i}(t + \mu) - C\_{j}(t)| \> 0$ if $\frac{\epsilon}{1 - \kappa} \leq \mu$.

I have no idea where he comes up with this, maybe my math isn't too great.

Note: $\mu$ is a constant that must be less than the shortest transmission time for interprocess messages.

PC1 implies $|C\_{i}(t + \mu) - C\_{i}(t)| \> (1 - \kappa)\mu$. This is apparent because (1 - $\kappa$) is less than 1. But apparently he combines this with PC2 to deduce the proposition.

How does he arrive at this??

# Answer
> 1 votes
The constraint as written by Lamport is $C\_i(t+\mu)-C\_j(t)\gt0$ or $C\_i(t+\mu)\gt C\_j(t)$ which can be re-written $$C\_i(t+\mu) - C\_i(t)\gt C\_j(t) - C\_i(t) \tag{\*}\label{\*}$$

Given Lamport's previous deductions, we recognise the boundary conditions each side must satisfy namely: $$(1-\kappa)\mu \lt C\_i(t+\mu) - C\_i(t)$$ $$ \epsilon \gt C\_j(t) - C\_i(t)$$

Now, Lamport wants to find out the range of values for 'variables' $\epsilon,\kappa$ ($\mu$ is fixed) that will ensure the strict inequality $\eqref{\*}$. Obviously, for real numbers (Lamport's starting assumption) if $x \lt A$ and $y \gt B$, then as long as $y \leq x$ we know $A\gt B$.

In other words, as long as $\epsilon \leq (1-\kappa)\mu$ then $\eqref{\*}$ is true and so $$C\_i(t+\mu)-C\_j(t)\gt0$$

---
Tags: algorithm-analysis, distributed-systems, clocks
---


# Question
Title: Is there an algorithm for random sampling from a priority queue with probability proportional to priority?
Suppose I want to randomly sample from a large set of items, each of which has a "score". I want my probability of sampling to be proportional to the score. One simple way to achieve this is divide each score by the total, then randomly sample based on each probability. This is at least O(N), and running it the next time will be O(N) as well since we have to renormalize. Inserting is also O(N) because we have to renormalize. I'm wondering if there is way we can utilize a priority queue or binary tree to make sampling and insertion less costly.

I am thinking for example, store every item in a priority queue, then to sample: Look at the current item's score, the left item's sum of scores, and the right item's sum of scores. Normalize by dividing each by the sum of all three, and sample the result. If the result is the left, rerun the algorithm on the left node. If the result is the right, rerun the algorithm on the right node. Otherwise if it's the current node, remove the node and return it as the sample. It is guaranteed to terminate when it gets to a leaf. We would have to do some extra work to keep track of the sum, but I think this would make all operations O(log(N)). Not sure this would sample with the actual required probability or if the time complexity is correct. Is there any existing work on this?

Edit: I think I found the answer: https://en.wikipedia.org/wiki/Reservoir\_sampling#Algorithm\_A-Res

# Answer
> 1 votes
This is exactly what the A-Res algorithm is for

If you have a positive weight for each sample, then you can achieve a probability of sampling proportional to the weight, even without knowing all of the other weights at a given time. The way you achieve this is:

* For each sample: randomly generate a number between from 0 to 1
* Raise the result to the power of (1/weight).

It can be shown that a sample with N times the weight of another sample is N times more likely to be greater (have higher priority)

---
Tags: probability-theory, sampling, priority-queues
---


# Question
Title: Minimum distance in an undirected weighted graph to cover k nodes using teleportations
I have been practicing problems on *graphs* and *shortest paths* and I encountered a problem that I'm struggling to understand.

Can you give me any tips and/or can you confirm that I got the general concept of the problem right?

> In a given undirected weighted graph $G=(V,E)$ and an integer $k$ and edges with positive weights, the starting point is node $v\_0$. You have to visit every node from $v\_0, v\_1, v\_2, \dots, v\_{k-1}$. If you visit any of those $k$ nodes you are allowed to create a portal in them. You can only make portals in those $k$ nodes. From one portal you can teleport to any other without any cost to the path.
>
> You have to create a function `double shortestPath(int k)` that returns a shortest path to visit all $k$ nodes using teleportation system (if necessary).

I sketched this graph and tried to understand the problem here. Lets say we have to visit nodes 0,1 and 2.

**Edited (Please check the reply to see better example of the problem)**

**My approach is this:** If I take this route $0 \to 5$ (cost 1) then $5 \to 4$ (cost 2), $4 \to 2$ (cost 3) and then jump from $2 \to 0$ and go $0 \to 1$ (cost 9). This is the shortest path using teleportations.

Can someone tell me if I understood this problem correctly and maybe give some tips on how to implement the algorithm?

# Answer
> 1 votes
You can do this in polynomial time with a greedy algorithm by always traveling to the nearest un-visited terminal, and dropping a portal in every terminal.

The crucial observations are these:

1. Since it's free to drop a portal and use one, you always put a portal in each of the terminals.
2. There is no point traveling anywhere but to a terminal.
3. When you move to a terminal, you always travel *from* the closest portal.

Let $G = (V, E, w)$ be the input graph and $T \subseteq V$ be your $k$ terminals, with $v\_0 \in T$.

Start with $T' = \\{v\_0\\}$. While $|T'|\<k$, pick a terminal *not in* $T'$ that is of shortest distance from $T'$ and add it to $T'$. Sum up the distances traveled in total.

Notice that you can preprocess your graph in $O(t^2 (n+m))$ time to get a new (complete) graph $G' = (T, E', w')$ with only vertices from $T$ and where the edge $t\_1t\_2$ has $w'(t\_1, t\_2) = \text{dist}\_G(t\_1, t\_2)$.

*Edit: This answer is updated. The previous answer was based on Steiner Tree.*

# Answer
> 0 votes
**Reply to @Pål GD:**

Lets try and apply Steiner algorithm to this graph where $b,e$ and $g$ are terminals. Starting point will be node $b$. Closest of nodes $e$ and $g$ to the node $b$ is node $e$ with cost of $6+7=13$. So, for now, we have a subgraph with nodes $b \rightarrow c \rightarrow e $ . Finally we need $g$ in our subgraph that will make a minimum spanning tree which would cover terminal nodes. The closest node in our graph to the node $g$ is $c$ with the cost $15$. Thus our final subgraph will look like this:

And this subgraph indeed covers all the terminal nodes with the cost of 28. But in the exercise with teleportation we are allowed to make a portal in nodes $b,e$ and $g$ after we visit them. In this case, our starting point is $b$ and we make a portal in it. Next node we visit is $c$ with the cost $6$, after that we go to the node $e$ with the cost $6+7=13$ and now we're allowed to make a portal in node $e$. So in this case it's better to teleport back to the node $b$ and go to the node $f$ via $c$ than going back from $e$ to $c$ and then to $f$ with the cost of $10$. Cost to $f$ in this case would be additional $9$ to current $13$ and we have total cost for now of $22$. Now we visit $d$ and finally $g$ with additional cost of $12$ and the final cost would be $34$ with our teleportation system.

With the Steiners algorithm I could use the subgraph to traverse it with portals (still have no effective idea of changing Steiners algorithm to work like this). But the problem is, if we take a look at the graph we see that the best possible subgraph would be made of nodes $b,a,d,g,c$ and $e$. Lets explain why.

We're starting from the node $b$ and traverse all to the node $g$ via nodes $a$ and $d$ with the cost of $16$. We have now two portals: one in $g$ and oen in $b$ so we're allowed to teleport back to $b$ with the cost of $0$. Then we can traverse to the node $e$ via nodes $c$ and $e$ with the cost of $13$ and the final cost would be $29$ which is better than $34$ of the previous case.

This would apply in the case I understood Steiner algorithm correctly and would be pleased if You could confirm it.

---
Tags: shortest-path, dijkstras-algorithm
---


title: Algorithm to compare two data sets

text:
# Question
Title: Algorithm to compare two data sets
I have two data sets of a particular structure:

```
User 1:
  Salad1: Tuna, Mayo, Lettuce
  ...
  Breakfast1: Egg, Avocado, Toast

User 2:
  Salad1: Tuna, Mayo
  ...
  Breakfast1: Egg, Toast, Sausage

```

There are thousands of dishes, and the goal is to ensure that all the ingredients from User 1 dish are present in the corresponding recipe of User 2 data set. We can't overwrite the recipe in User 2 data set, removing their additions - we only need to ensure that the ingredients from the corresponding User 1 dishes are present, and add them in if they are absent.

**My solution:**

Create a list of hashes for each recipe from each User:

```
Salad1|Tuna~Mayo~Lettuce
Breakfast1|Egg~Avocado~Toast

```

Perform a 'difference' operation on the two string arrays and end up with a list of those recipies that don't match. Break away the dish identifier from each resulting string, find the dish in the second data set and append the missing ingridient.

**Benefits of my solution**

As you can see, once we add the 'Lettuce' to the Salad1 recipe of User2, the relevant dish will stop coming up in the 'Difference of hashes' output, and the consequent synchronisations will take much less time.

**Problems with my solution**

Sadly, the Breakfast1 recipe of User2 will keep flagging up the difference even after we add the 'Toast' entry to it, because here the user has added 'Sausage' to the list. This way, if User2 chooses to add a 'special ingridient' to each recipe we will end up evaluating every single dish in his database for having ingridients of the corresponding dish in User1 data set.

**Essentially**: my approach reduces the amount of individual dishes that I need to evaluate (iterate over ingridients to see if the ingridients from the User1 dataset are present), but I still need to evaluate those where extra ingridients were added.

**The challenge**

Is there any established **algorithm** that would take the two datasets above, and return only 'dishes' from the second data set that need 'ingridients' added to them?

# Answer
> 3 votes
I think you are asking about how to implement a set difference operation. Specifically, if user 1's recipe for salad 1 is viewed as a set of ingredients A, and user 2's recipe for salad 1 is viewed as a set of ingredients B, then the the set difference A \ B is exactly the set of ingredients that are in A but not in B.

One well-known and particularly simple algorithm goes like this:

1. Sort each list of ingredients (let's say in ascending order).
2. At the start, the first element of each list is the current element.
3. Repeatedly compare the current elements of the lists. Calling the current elements of A and B by the names a and b, respectively, there are three cases:
    * **a \< b** Ingredient a is in A and not in B, so make a note of it. Advance the current element for A, but keep the same current element in B.
    * **a = b** Ingredient a is in both, so nothing special need be done. Advance both current elements.
    * **a \> b** Ingredient b is in B and not in A. We don't need to do anything special to rectify this situation. Advance the current element in B.

When you reach the end of both sorted lists, you will have a record of the ingredients that must be added to B's recipe.

There are more complicated algorithms that exploit the fact that strings support more interesting observations than just comparison, or which can take advantage of situations where there's only a small collection of possible ingredients, but I recommend you start here until you're confident that this algorithm doesn't meet your performance needs.

---
Tags: data-structures, comparison
---


# Question
Title: Why isn't there a .= operator? (or ->= etc)
Considering how often we do:

```
variable = variable + another;
variable = variable - another;
variable = variable * another;
variable = variable / another;
variable = variable & another;
variable = variable | another;
variable = variable ^ another;

```

we then made the following language shortcuts:

```
variable += another;
variable -= another;
variable *= another;
variable /= another;
variable &= another;
variable |= another;
variable ^= another;

```

so, then, considering how often we do this:

```
variable = variable.different();
// or variable = variable->different();
// or variable = variable::different();

```

(for instance, `stringVar = stringVar.toUpperCase()`), why isn't there one of these?

```
variable .= different();
// or variable ->= different();
// or variable ::= different();

```

is it a parsing issue? Would it be too hard? Or is there some obvious thing I don't see here?

I'm *not* asking for opinions, here. I want to know if there's any documented, historic, technical, or other verifiable reasons for why there is no such operator.

# Answer
> 6 votes
IMO, the biggest reason is that identifiers are not first class values in programming languages and "." is not a real operator like `+` or `-` are. For example, you can't convert

```
var foo = variable.bar()

```

into

```
var name = bar
var foo = variable.name()

```

The same way you can convert

```
var foo = 1 + 10

```

into

```
var x = 10
var foo = 1 + x

```

In more technical terms, in most languages `x + y` is an *expression*, while `x`, `x.y` and `x[i]` are *identifiers*.

Summing up, when using your hypothetical `.=`, the right hand side needs to be interpreted as a field name, not an expression. This leads to unintuitive results - the following two lines look very similar but do wildly different things.

```
x += bar() // calls the bar() global function and add its value to x
y .= bar() // calls y's bar() method, and sets `y` to its result.

```

---

Additionally, as Guy Coder pointed out, when using `+`, `-`, etc its guaranteed that the type of the resulting expression is the same as the arguments so `+=` always makes sense. On the other hand, we can have `y.bar()` return a type different from `y`, in which case `.= bar()` would make no sense.

# Answer
> 3 votes
In the situtation: `variable += another;` you have 2 variables, 1 operator and 1 assignment.

In the situtation: `variable ->= different()` you have 1 variable, 1 method access operator ( i.e -\>), 1 method name that needs to be called and 1 assignment.

When a language's *syntactic sugar* feature is designed, one important concept to consider is composition, i.e how elegantly you can compose these syntactic sugar based expressions.

In the first example you can create a chain of these operations:

```
variable *= another_var -= variable += another;

```

Whereas there is no simple way to do this kind of composition in the second case. Lets say we have the below code:

```
variable = variable.method1();
another_var = variable.method2(params);

```

If you try to apply the approach that you suggested, you will get into weird situtation:

```
another_var .= <what should be here> variable .= method1()

```

In the method based case there is pattern called "fluent API design". You can use that to express the above code elegantly.

```
another_var = variable.method1().method2(params);

```

Hope this helps.

# Answer
> 3 votes
The reason it is not done is because the type of the result may not be the same as the type of the receiving term.

In the examples you gave the result and receiving terms are the same type or it is common to coerce the type of the result into the receiving term type which is common with mathematical operators.

Standard way
Int = Int + Int

Syntactic sugar
Int += Int

```
Receiving Term  Other Term  Result
Int             Int         Int
Float           Int         Float
Float           Float       Float

```

If it is taken that -\> means pointer then you would have

Standard way
Name = Person -\> Name

Your way
Person -\>= Name

```
Receiving Term  Other Term  Result
Object          String      String

```

So setting an object to a string would either cause the type of the object to become a string which may not be desired or the compiler might throw an exception.

Standard way
Color = Bird -\> Color

Your way
Bird -\>= Color

```
Receiving Term  Other Term  Result
Bird            Color       Color

```

Obviously a bird should not be a color but can have a color.

# Answer
> 2 votes
The simple thing is we rarely found this situation for using like this

```
 variable = variable.different();
// or variable = variable->different();
// or variable = variable::different();

```

since we call a function with objects and assign the return value to the variable and normally we never return an object back to the same in old days.

there fore the compiler designer will never think about giving special meaning to the `.=` or `->=`

but if you take the examples of arithmetic operators we will found this may be in every program like tormenting adding etc .

but when the concept of OOP is increased rapidly one need to think about giving such a special meaning..

# Answer
> 1 votes
I would like to build on hugomg with this example from JavaScript:

```
var foo = variable.bar()

```

can be rewritten as

```
var name = "bar";
var foo = variable[name]();

```

When it comes down to it, `.` is just as much an operator as `+`. It's a binary operator who's left side must be an object, and who's right side should be a property name in that object. In ES at least, for property names that don't fit the identifier requirements, there's a different notation that does the same thing.

Further, while `x` is an identifier and `y` is also an identifier, `x.y` is an expression, not significantly different from `1+2` except in how it is carried out. The simple fact that the `.` operation can be interfered with (via Proxy) is proof that `x.y` is not simply an identifier.

The real reason why `.=` is not an operator is simply that it makes code harder to read and understand, even for the engine. Consider this:

```
function add(a=0, b=0) {
  return a + b;
}

some.preexisting.obj.with.an.add.function .= add(3);

```

This would be valid code, but confusing as heck. Without the dot in `.=`, the add function in this example would be called. However, with it, the add function belonging to that ridiculous object would be called. This goes against some basic understandings about the nature of ES function calls. In short, it's just a bad idea.

---
Tags: programming-languages, language-design
---


# Question
Title: What is the combinatorial reasoning for the $n$ factor in $n \times n! / (b!(n - b)!)$?
I am currently studying the textbook *Artificial Intelligence: A Modern Approach, 4th Edition*, by Russell and Norvig. **Chapter 3 Solving Problems by Searching** says the following:

> Another type of grid world is the **sokoban puzzle**, in which the agent's goal is to push a number of boxes, scattered about the grid, to designated storage locations. There can be at most one box per cell. When an agent moves forward into a cell containing a box and there is an empty cell on the other side of the box, then both the box and the agent move forward. The agent can't push a box into another box or a wall. For a world with $n$ non-obstacle cells and $b$ boxes, there are $n \times n! / (b!(n - b)!)$ states; for example on an $8 \times 8$ grid with a dozen boxes, there are over 200 trillion states.

I understand the combinatorial reasoning for why we get $n! / (b!(n - b)!)$ (the binomial coefficient), since we are looking for the number of ways we can choose (with replacement) $b$ boxes from a world with $n$ non-obstacle cells. But I don't understand where the $n$ factor in $n \times n! / (b!(n - b)!)$ comes from. What is the combinatorial reasoning for this $n$ factor?

# Answer
Part of the state of the world is the location of the agent. Since there are $n$ cells, this variable has $n$ possible values, producing the factor of $n$.

Actually, there may be a mistake in Russell and Norvig's formula. After we have chosen the location of the agent, there are only $n - 1$ possible locations for the $b$ boxes, giving us $(n - 1)! / (b! (n - b - 1)!)$ choices for where to put all of the boxes. So, the number of states is $n \times (n - 1)!/(b!(n - b - 1)!)$, which simplifies to $n! / (b! (n - b - 1)!)$. (This is the trinomial coefficient $n \choose 1, b$.)
> 1 votes

---
Tags: combinatorics, artificial-intelligence
---