# Question
Title: Why is quicksort better than other sorting algorithms in practice?
In a standard algorithms course we are taught that **quicksort** is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ in the worst case (like **mergesort** and **heapsort**), and even linear time in the best case (like **bubblesort**) but with some additional needs of memory.

After a quick glance at some more running times it is natural to say that quicksort **should not** be as efficient as others.

Also, consider that students learn in basic programming courses that recursion is not really good in general because it could use too much memory, etc. Therefore (and even though this is not a real argument), this gives the idea that quicksort might not be really good because it is a recursive algorithm.

**Why, then, does quicksort outperform other sorting algorithms in practice?** Does it have to do with the structure of *real-world data*? Does it have to do with the way memory works in computers? I know that some memories are way faster than others, but I don't know if that's the real reason for this counter-intuitive performance (when compared to theoretical estimates).

---

**Update 1:** a canonical answer is saying that the constants involved in the $O(n\log n)$ of the average case are smaller than the constants involved in other $O(n\log n)$ algorithms. However, I have yet to see a proper justification of this, with precise calculations instead of intuitive ideas only.

In any case, it seems like the real difference occurs, as some answers suggest, at memory level, where implementations take advantage of the internal structure of computers, using, for example, that cache memory is faster than RAM. The discussion is already interesting, but I'd still like to see more detail with respect to memory-management, since it appears that *the* answer has to do with it.

---

**Update 2:** There are several web pages offering a comparison of sorting algorithms, some fancier than others (most notably sorting-algorithms.com). Other than presenting a nice visual aid, this approach does not answer my question.

# Answer
# Short Answer

The cache efficiency argument has already been explained in detail. In addition, there is an intrinsic argument, why Quicksort is fast. If implemented like with two “crossing pointers”, e.g. here, the inner loops have a very small body. As this is the code executed most often, this pays off.

# Long Answer

First of all,

## *The* Average Case does not exist!

As best and worst case often are extremes rarely occurring in practice, average case analysis is done. But any average case analysis assume some **distribution of inputs**! For sorting, the typical choice is the *random permutation model* (tacitly assumed on Wikipedia).

## Why $O$-Notation?

Discarding constants in analysis of algorithms is done for one main reason: If I am interested in *exact* running times, **I need (relative) costs of all involved basic operations** (even still ignoring caching issues, pipelining in modern processors ...). Mathematical analysis can *count* how often each instruction is executed, but running times of single instructions depend on processor details, e.g. whether a 32-bit integer multiplication takes as much time as addition.

There are two ways out:

1. **Fix some machine model.**

This is done in Don **Knuth**'s book series “The Art of Computer Programming” for an artificial “typical” computer invented by the author. In volume 3 you find exact **average case results** for many sorting algorithms, e.g.

* Quicksort: $ 11.667(n+1)\ln(n)-1.74n-18.74 $
    * Mergesort: $ 12.5 n \ln(n) $
    * Heapsort: $ 16 n \ln(n) +0.01n $
    * Insertionsort: $2.25n^2+7.75n-3ln(n)$
    \[source\]

These results indicate that Quicksort is fastest. But, it is only proved on Knuth's artificial machine, it does not necessarily imply anything for say your x86 PC. Note also that the algorithms relate differently for small inputs:
\[source\]
2. **Analyse abstract *basic operations*.**

For comparison based sorting, this typically is *swaps* and *key comparisons*. In Robert Sedgewick's books, e.g. “Algorithms”, this approach is pursued. You find there

* Quicksort: $2n\ln(n)$ comparisons and $\frac13n\ln(n)$ swaps on average
    * Mergesort: $1.44n\ln(n)$ comparisons, but up to $8.66n\ln(n)$ array accesses (mergesort is not swap based, so we cannot count that).
    * Insertionsort: $\frac14n^2$ comparisons and $\frac14n^2$ swaps on average.

As you see, this does not readily allow comparisons of algorithms as the exact runtime analysis, but results are independent from machine details.

## Other input distributions

As noted above, average cases are always with respect to some input distribution, so one might consider ones other than random permutations. E.g. research has been done for Quicksort with equal elements and there is nice article on the standard sort function in Java
> 260 votes

# Answer
There are multiple points that can be made regarding this question.

**Quicksort is usually fast**

Although Quicksort has worst-case $O(n^2)$ behaviour, it is usually fast: assuming random pivot selection, there's a very large chance we pick some number that separates the input into two similarly sized subsets, which is exactly what we want to have.

In particular, even if we pick a pivot that creates a 10%-90% split every 10 splits (which is a meh split), and a 1 element - $n-1$ element split otherwise (which is the worst split you can get), our running time is still $O(n \log n)$ (note that this would blow up the constants to a point that Merge sort is probably faster though).

**Quicksort is usually faster than most sorts**

Quicksort is usually faster than sorts that are slower than $O(n \log n)$ (say, Insertion sort with its $O(n^2)$ running time), simply because for large $n$ their running times explode.

A good reason why Quicksort is so fast in practice compared to most other $O(n \log n)$ algorithms such as Heapsort, is because it is relatively cache-efficient. Its running time is actually $O(\frac{n}{B} \log (\frac{n}{B}))$, where $B$ is the block size. Heapsort, on the other hand, doesn't have any such speedup: it's not at all accessing memory cache-efficiently.

The reason for this cache efficiency is that it linearly scans the input and linearly partitions the input. This means we can make the most of every cache load we do as we read every number we load into the cache before swapping that cache for another. In particular, the algorithm is cache-oblivious, which gives good cache performance for every cache level, which is another win.

Cache efficiency could be further improved to $O(\frac{n}{B} \log\_{\frac{M}{B}} (\frac{n}{B}))$, where $M$ is the size of our main memory, if we use $k$-way Quicksort. Note that Mergesort also has the same cache-efficiency as Quicksort, and its k-way version in fact has better performance (through lower constant factors) if memory is a severe constrain. This gives rise to the next point: we'll need to compare Quicksort to Mergesort on other factors.

**Quicksort is usually faster than Mergesort**

This comparison is completely about constant factors (if we consider the typical case). In particular, the choice is between a suboptimal choice of the pivot for Quicksort versus the copy of the entire input for Mergesort (or the complexity of the algorithm needed to avoid this copying). It turns out that the former is more efficient: there's no theory behind this, it just happens to be faster.

Note that Quicksort will make more recursive calls, but allocating stack space is cheap (almost free in fact, as long as you don't blow the stack) and you re-use it. Allocating a giant block on the heap (or your hard drive, if $n$ is *really* large) is quite a bit more expensive, but both are $O(\log n)$ overheads that pale in comparison to the $O(n)$ work mentioned above.

Lastly, note that Quicksort is slightly sensitive to input that happens to be in the right order, in which case it can skip some swaps. Mergesort doesn't have any such optimizations, which also makes Quicksort a bit faster compared to Mergesort.

**Use the sort that suits your needs**

In conclusion: no sorting algorithm is always optimal. Choose whichever one suits your needs. If you need an algorithm that is the quickest for most cases, and you don't mind it might end up being a bit slow in rare cases, and you don't need a stable sort, use Quicksort. Otherwise, use the algorithm that suits your needs better.
> 101 votes

# Answer
In one of the programming tutorials at my university, we asked students to compare the performance of quicksort, mergesort, insertion sort vs. Python's built-in list.sort (called Timsort). The experimental results surprised me deeply since the built-in list.sort performed so much better than other sorting algorithms, even with instances that easily made quicksort, mergesort crash. So it's premature to conclude that the usual quicksort implementation is the best in practice. But I'm sure there much better implementation of quicksort, or some hybrid version of it out there.

This is a nice blog article by David R. MacIver explaining Timsort as a form of adaptive mergesort.
> 56 votes

# Answer
I think one of the main reasons why QuickSort is so fast compared with other sorting algorithms is because it's cache-friendly. When QS processes a segment of an array, it accesses elements at the beginning and end of the segment, and moves towards the center of the segment.

So, when you start, you access the first element in the array and a piece of memory (“location”) is loaded into the cache. And when you try to access the second element, it's (most likely) already in the cache, so it's very fast.

Other algorithms like heapsort don't work like this, they jump in the array a lot, which makes them slower.
> 41 votes

# Answer
Others have already said that the asymptotic *average* runtime of Quicksort is better (in the constant) than that of other sorting algorithms (in certain settings).

What does that mean? Assume any permutation is chosen at random (assuming uniform distribution). In this case, typical pivot selection methods provide pivots that *in expectation* divide the list/array roughly in half; that is what brings us down to $\cal{O}(n \log n)$. But, additionally, *merging* partial solutions obtained by recursing takes only constant time (as opposed to linear time in case of Mergesort). Of course, separating the input in two lists according to the pivot is in linear time, but it often requires few actual swaps.

Note that there are many variants of Quicksort (see e.g. Sedgewick's dissertation). They perform differently on different input distributions (uniform, almost sorted, almost inversely sorted, many duplicates, ...), and other algorithms might be better for some.

Another fact worth noting is that Quicksort is *slow* on short inputs compared to simper algorithms with less overhead. Therefore, good libraries do not recurse down to lists of length one but will use (for example) insertion sort if input length is smaller than some $k \approx 10$.
> 31 votes

# Answer
In comparison to other comparison-based sorting algorithms with $O(n \lg n)$ time complexity, quick-sort is often considered to better than other algorithms like merge-sort because it is an in-place sorting algorithm. In other words, we don't need (much more) memory to store the members of the array.

ps: to be precise, being better than other algorithms is task dependent. For some tasks it might be better to use other sorting algorithms.

See also:
> 24 votes

# Answer
My experience working with real world data is that **quicksort is a poor choice**. Quicksort works well with random data, but real world data is most often not random.

Back in 2008 I tracked a hanging software bug down to the use of quicksort. A while later I wrote simple implentations of insertion sort, quicksort, heap sort and merge sort and tested these. My merge sort outperformed all the others while working on large data sets.

Since then, merge sort is my sorting algorithm of choice. It is elegant. It is simple to implement. It is a stable sort. It does not degenerate to quadratic behaviour like quicksort does. I switch to insertion sort to sort small arrays.

On many occasions I have found my self thinking that a given implementation works surprisingly well for quicksort only to find out that it actually isn't quicksort. Sometimes the implementation switches between quicksort and another algorithm and sometimes it does not use quicksort at all. As an example, GLibc's qsort() functions actually uses merge sort. Only if allocating the working space fails does it fall back to in-place quicksort which a code comment calls "the slower algorithm".

Edit: Programming languages such as Java, Python and Perl also use merge sort, or more precisely a derivative, such as Timsort or merge sort for large sets and insertion sort for small sets. (Java also uses dual-pivot quicksort which is faster than plain quicksort.)
> 22 votes

# Answer
Even though quick-sort has a worst case run time of $\Theta(n^2)$, quicksort is considered the best sorting because it is VERY efficient on the average: its expected running time is $\Theta(n\log n)$ where the constants are VERY SMALL compared to other sorting algorithms. This is the main reason for using quick sort over other sorting algorithms.

The second reason is that it performs `in-place` sorting and works very well with virtual-memory environments.

**UPDATE:** : (After Janoma's and Svick's comments)

To illustrate this better let me give an example using Merge Sort (because Merge sort is the next widely adopted sort algorithm after quick sort, I think) and tell you where the extra constants come from (to the best of my knowledge and why I think Quick sort is better):

Consider the following seqence:

```
12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

```

If you care fully look how the last stage is happening, first 12 is compared with 8 and 8 is smaller so it goes first. Now 12 is AGAIN compared with 21 and 12 goes next and so on and so forth. If you take the final merge i.e. 4 elements with 4 other elements, it incurs a lot of EXTRA comparisons as constants which is NOT incurred in Quick Sort. This is the reason why quick sort is preferred.
> 19 votes

# Answer
## Under what conditions is a specific sorting algorithm actually the fastest one?

1. When implemented in a **parallel way in hardware**, does it need to have a reasonably **low latency** while requiring as **few gates as possible**?

**Yes,** use a **bitonic sorter or Batcher odd-even mergesort**, latency is $\Theta(\log(n)^2)$ and the number of comparators and multiplexers is $\Theta(n \cdot \log(n)^2)$.
2. How many different values can each element have? **Can every possible value have assigned a unique place in memory or cache**?

**Yes,** use **count sort or radix sort**, those usually have a linear runtime of $\Theta(n \cdot k)$ (count sort) or $\Theta(n \cdot m)$ (bucket sort) but slow down for a large number of different values, as $k=2^{\\#number\\\_of\\\_Possible\\\_values}$ and $m = \\#maximum\\\_length\\\_of\\\_keys$.
3. Does the underlying data structure consist of **linked elements**?

**Yes,** always use **in-place merge sort**. There are both easy to implement fixed size or adaptive (a.k.a. natural) bottom-up in place merge sorts of different arities for linked data structures, and since they never require copying the entire data in each step and they never require recursions either, they are faster than any other general comparison-based sorts, even faster than quick sort.
4. Does the **sorting need to be stable**?

**Yes,** use **mergesort**, either in place or not, fixed-size or adaptive, depending on the underlying data structure and the kind of data to be expected, even in cases where quick sort would otherwise be preferred, as stabilizing an arbitrary sorting algorithm requires $\Theta(n)$ additional memory in the worst case consisting of original indexes, which also needs to be kept in sync with each swap that is to be performed on the input data, so that every performance gain that quick sort might have over merge sort is probably thwarted.
5. Can the size of the underlying **data be bound to a small to medium size**? e.g. Is **n \< 10,000...100,000,000** (depending on the underlying architecture and data structure)?

use **bitonic sort or Batcher odd-even mergesort**. Go to **#1**
6. Can you **spare another $\Theta(n)$ memory**?

**Yes**

* Does the input data consist of **large pieces of already sorted sequential data**?
    * use **adaptive (aka natural) merge sort** or **timsort**
    * Does the input data mostly consist of elements that are **almost in the correct place**?
    * Use **bubble sort** or **insertion sort.** If you fear their $\Theta(n^2)$ time complexity (which is pathological for almost sorted data), maybe consider switching to shell sort with an (almost) asymptotically optimal sequence of gaps, some sequences that yield $\Theta(n \cdot \log(n)^2)$ worst case run time are known, or maybe try comb sort. I'm not sure either shell sort or comb sort would perform reasonably good in practice.

**No**

* Can you **spare another $\Theta(\log(n))$ memor**y? **Yes**
    * Does the **underlying data structure allow for directed sequential access or better?**
    * Yes

    + Does it allow only a single sequence of read/write accesses at a time up till the end of the data has been reached (e.g. directed tape access)?
        + Yes, use **merge sort**, but there is no obvious way to make this case in place, so it may require additional $\Theta(n)$ memory. But if you have time and the balls to do it, there is a way to merge 2 arrays in $\Theta(n)$ time using only $\Theta(\log(n))$ space in a stable way, according to Donald E. Knuth "The Art of Computer Programming, Volume 3: Sorting and Searching", exercise 5.5.3. states that there is an algorithm by L. Trabb-Pardo that does so. However, I doubt this would be any faster than the naive mergesort version or the quicksort from the case above.
        + No, it allows **multiple simultaneous accesses to a sequence of data** (e.g. is not a tape drive) use **quicksort**, for practical purposes I would recommend either a randomized or an approximated median one. If you are wary of pathological $\Theta(n^2)$ cases, consider using intro sort. If you are hell-bent on deterministic behavior, consider using the median-of-median algorithm to select the pivot element, it requires $\Theta(n)$ time and its naive implementation requires $\Theta(n)$ space (parallelizable), whereas it may be implemented to only require $\Theta(\log(n))$ space (not parallelizable). However, the median-of-median algorithm gives you a deterministic quicksort which has worst-case $\Theta(n \cdot \log(n))$ run-time.
    * No, **you're screwed** (sorry, we need at least 1 way of accessing each data element once)

    + No, Can you spare a **small constant amount of memory**?
        + Yes, Does the **underlying data structure allow for random access**?
            - Yes, use **heapsort**, it has an asymptotic optimal run-time of $\Theta(n \cdot \log(n))$, but dismal cache coherency and doesn't parallelize well.
            - No, you are **screwed**
        + No, you are **screwed**

## Implementation hints for quicksort

* Naive binary quicksort requires $\Theta(n)$ additional memory, however, it is relatively easy to reduce that down to $\Theta(\log(n))$ by rewriting the last recursion call into a loop. Doing the same for k-ary quicksorts for k \> 2 requires $\Theta(n^{\log\_k(k-1)})$ space (according to the master theorem), so binary quicksort requires the least amount of memory, but I would be delighted to hear if anyone knows whether k-ary quicksort for k \> 2 might be faster than binary quicksort on some real world setup.
* There exist bottom-up, iterative variants of quicksort, but AFAIK, they have the same asymptotic space and time boundaries as the top-down ones, with the additional down sides of being difficult to implement (e.g. explicitly managing a queue). My experience is that for any practical purposes, those are never worth considering.

## Implementation hints for mergesort

* bottom-up mergesort is always faster than top-down mergesort, as it requires no recursion calls.
* the very naive mergesort may be sped up by using a double buffer and switch the buffer instead of copying the data back from the temporal array after each step.
* For many real-world data, adaptive mergesort is much faster than a fixed-size mergesort.
* the merge algorithm can easily be parallelized by splitting the input data into k approximately same-sized parts. This will require k references into data, and it is a good thing to choose k such that all of k (or c\*k for a small constant c \>= 1) fit into the nearest memory hierarchy(usually L1 data cache). Choosing the smallest out of k elements the naive way(linear search) takes $\Theta(k)$ time, whereas building up a min-heap within those k elements and choosing the smallest one requires only amortized $\Theta(\log(k))$ time (picking the minimum is $\Theta(1)$ of course, but we need to do a little maintenance as one element is removed and replaced by another one in each step).
* The parallelized merge always requires $\Theta(n)$ memory regardless of k.
* From what I have written, it is clear that quicksort often isn't the fastest algorithm, except when the following conditions all apply:
* there are more than a "few" possible values
* the underlying data structure is not linked
* we do not need a stable order
* data is big enough that the slight sub-optimal asymptotic run-time of a bitonic sorter or Batcher odd-even mergesort kicks in
* the data isn't almost sorted and doesn't consist of bigger already sorted parts
* we can access the data sequence simultaneously from multiple places
* memory writes are particularly expensive (because that's mergesort's main disadvantage), so far as it slows down the algorithm beyond a quicksort's probable sub-optimal split. or we can only have $\Theta(\log(n))$ additional memory, $\Theta(n)$ is too much (e.g. external storage)
> 18 votes

# Answer
**1 -** Quick sort is inplace (doesn't need extra memmory, other than a constant amount.)

**2 -** Quick sort is easier to implement than other efficient sorting algorithms.

**3 -** Quick sort has smaller constant factors in it's running time than other efficient sorting algorithms.

Update: For merge sort, you need to do some "merging," which needs extra array(s) to store the data before merging; but in quick sort, you don't. That's why quick sort is in-place. There are also some extra comparisons made for merging which increase constant factors in merge sort.
> 17 votes

# Answer
Most of the sortings methods have to move data around in short steps (for example, merge sort makes changes locally, then merges this small piece of data, then merges a bigger one. ..). In consequence, you need many data movements if data is far from its destination.

Quicksort, on the other side tries to interchange numbers that are in the first part of the memory and are big, with numbers that are in the second part of the array and are small (if you are sorting $a \le b$, the argument is the same in the other sense), so they get quickly allocated near their final destination.
> 11 votes

# Answer
You switched in your question from "is better" to "has better runtime". These are not the same. If you look at the other answers, you will find that Mergesort might run faster - but Quicksort has the advantage that it uses negligible space for things other than the array to be sorted. That means I can call it without fear of running out of memory, no matter how large the array is. That is not quite true for Mergesort, if the data can be close in size to the available data. And if virtual memory is available, Mergesort can take a lot longer due to paging.

In practice you wouldn't just use a O (n log n) algorithm, you would check if you can do things faster in special cases. If your array is mostly ascending or mostly descending with few exceptions, it can be sorted in linear time. (If let's say all but 1/8th of the values are in ascending order, it can be sorted in O (n log n), but much faster than using Quicksort or Mergesort).

If you go a bit further: If your array consists of an initial part that is mostly sorted, a middle part, and an end part that is mostly sorted, and the middle part is substantially smaller than the whole array, then we can sort the middle part with Quicksort or Mergesort, and combine the result with the sorted initial or end parts. However, this doesn't affect the question, because the middle part can still be sorted with Quicksort or Mergesort.

Another question is: Can the work be multi-threaded? The partitioning is hard to divide between two threads. Once the array is partitioned, each half can easily be handled by a separate thread. If you have many threads, being able to use only one for the initial partitioning is painful. With Mergesort, we can also do many smaller merges using many threads. We have the advantage that a single merge can also be run in parallel by one thread producing the lower half of the sorted array, and another thread working from the high values down, producing the higher half of the sorted array. I think this gives a large advantage to Mergesort if many threads are available.
> 5 votes

---
Tags: algorithms, sorting
---


# Question
Title: Can an NP-Complete problem be reduced to an NP problem?
All NP problems can be reduced to NP-Complete problems, can an NP-Complete problem be reduced to a NP problem (non complete)?

# Answer
An NP-complete problem is in NP, by definition. No reduction needed.
> 4 votes

---
Tags: np-complete, reductions, np
---


# Question
Title: Are files download times actually unknowable due to the halting problem?
When downloading a file from the internet to our computer we are usually prompted with an estimate of how long it will take for the file to be downloaded.

From the Halting Problem, we know that $\mathrm{HALT}\_{\mathrm{TM}}$ is undecidable, where:

$\mathrm{HALT}\_{\mathrm{TM}} =\\{⟨M,w⟩\mid M \text{ is a TM and }M\text{ halts on input }w \\} $

Assuming that we can neglect the lack of infinite memory, we can model our computer writing on the disk as a Turing Machine $M$ and take the string encoding of the downloaded file as the input $w$. (More precisely, $w$ should be the string obtained composing the packets sent by the network)

From the Halting Problem it follows that it's not only impossible to know when the download will end, it's even impossible to know whether the download will ever end.

So, are files download times actually unknowable due to the halting problem? If not, where the above reasoning fails?

# Answer
Not at all.

The halting problem says it is impossible to decide whether an **arbitrary** turing machine with **arbitrary** input will halt. But there are many, many **specific** turing machines where we can prove that they halt for every input, or where we can look at the input and decide if the turing machine will halt or not.

And since the people writing the download code surely wrote it in such a way that it is guaranteed to finish for every import, there will be a proof that it is guaranteed to finish.
> 4 votes

# Answer
The main issue, I think, is that you have reduced your unknown problem (file download times) to a hard problem (the Halting Problem), showing that if you had some efficient algorithm for solving the hard problem, then the unknown problem would also be efficiently solvable. To prove hardness of the unknown problem, you need a reduction that goes the other way, by showing that efficiently solving the unknown problem would allow you efficiently solve the hard problem.

(A secondary issue is that I don't really see any way to express the "file download time" problem purely in terms of abstract Turing machines, since the problem itself seems so essentially tied to the physical world.)
> 2 votes

# Answer
Solving the "download time problem" is just impossible. Nothing says if your machine (or the network, or the origin, or...) will (or won't) crash, or get overloaded (perhaps everybody in India wakes up with the urge to get the same file, and crash the server) or slow to a crawl, or just speed up to a breeze, halfway through.

The problem here is that the actual time depends on a myriard of variables, many of them unknown (and unknowable), due to the immense complexity of the Internet and it millions of users (and lots of other external factors that can impact it's functioning).

The halting problem for Turing machines is quite different, there the pieces and their relationship is clear, simple and well-defined. By design, really: Turing was looking for a transparent model of what it means for a human to "compute" something, and distilled it down to a extremely minimal, simple one.
> 2 votes

---
Tags: turing-machines, halting-problem
---


# Question
Title: Cores, threads and sockets: what does it mean the calculation $T = tcs$ and the number on windows task manager performance?
Well, suppose then we have an CPU system such as:

> Thread(s) per core $\equiv t$ : 4
>
> Core(s) per socket $\equiv c$: 4
>
> Socket(s) $\equiv s$: 1

Then, we must to perform a simple calculation such as: $ 4 \cdot 4 \cdot 1 = 16 $

Therefore, in general we have:

$$ T = t\cdot c \cdot s \tag{1}$$

I guess that the equation $(1)$ gives you then the total number of threads which your system can handle simultaneously.

On the other hand, consider the figure, of windows task manager, in the following:

In the red box we clearly see the number of "Threads". So I would like to know:

**What is the difference between the number given by formula $(1)$ and the number given by windows task manager?**

# Answer
There are two kind of threads, hardware and software threads. The threads number shown in red box is the number of software threads. The threads calculated above(16) is the number of hardware threads.

A processor consists of multiple functional blocks like, register sets, integer ALU, floating point ALU, instruction decoder, instruction fetch units... In a pipelined processor supporting superscalar architecture (also known as hyperthreading or HT on Intel processors), instructions from multiple software threads can be in different phase of execution at the same point of time. The number of software threads instruction sequence which can be concurrently executing in a single processor core is defined by the hardware and are known as logical threads. Look at SMT threads for more clarity.

The number of threads shown is red box or software threads are the total number spawn threads. At most, 16 of them can be executing at the same point of time on the specified hardware. Operating system schedule software threads (in 1000's) on the available processors using some scheduling policy.
> 1 votes

---
Tags: cpu, process-scheduling, multi-tasking
---


title: acyclic and disjoint union

text:
# Question
Title: acyclic and disjoint union
I would like to find a prove of (a) so that the two E are acyclic and disjoint union and I dont unterstand b Could someone shed light on this problem, preferably spiced with some intuition?

Thanks, DarkDragon.

# Answer
> 0 votes
You can solve the first part by providing a valid topological ordering of the vertices, which shows that the graph is a DAG. To show that the union is equal to $E$ show that each arc in $E$ belongs to one of the two sets

The second part needs more context, what is OPT here?

---
Tags: approximation
---


# Question
Title: Find main memory location in cache(direct mapping)
Consider main memory of the size 64 kB with each word being 8 bits(one byte) only and a direct mapping Cache memory of size 4 kB also having data word size 8 bits.

Find the following :

* 1. Find the size of tag and index fields of cache?
* 2. In what location of cache hexadecimal address to main memory (AABB) (if exists in cache) will be located?

# Answer
> 2 votes
Answer to your first question is 4 tag bits and cache index bits should be 4 as it is byte-addressable so address bus size is 8 bits so the physical address is therefore of 8 bits and **cache index = physical address - tag bits**. Approach : **tag bits = lg(main-memory size/ cache-memory size)**. Also clarifying the question will help, I don't think memory is byte-addressable if at all 2nd question has to make sense since **AABB** will take 16-bit address bus. Or according to the question, it won't exist.

---
Tags: cpu-cache
---


# Question
Title: Algorithm for implementing the modulus "%" operator?
How can an efficient modulus operator be implemented?

Here's a naive way of defining `A % B`:

> given $(a,b) \in \mathbb{Z}$ (represented as `int`)
>
> while $a \> b$ : $(a,b) \mapsto (a-b,b)$
>
> return $a$

This could be very slow. E.g. $(a,b) = (10^7, 13)$. I could be subtracting 13's for a long time.

---

One more possibility is that `%` is defined in terms of another infix operator `/` as well as the `int` function (here in  and verbatim in Python):

> `a % b = a - (b * int(a/b))`

---

This is probably not how Python implements it's modulus operator (as it makes a call to C or Fortran). The `%` operator is need to reduce fractions or compute GCD's.

Here are some examples of truncation and division from Wikipedia:

# Answer
You don’t “implement the modulus operator”. You check wit the standards for your programming language how it is defined, and that’s what you implement. For languages like C, C++, Objective-C, Swift and many others, a % b is *defined* as a - b * (a/ b). And that’s what you implement.

To be efficient: Most processors have built-in division and multiplication. Many support faster implementation of division if b is known. And at last if you want to know whether a % b = 0, you can do that without calculating a / b exactly which makes it a bit faster.
> 4 votes

# Answer
My own mathematical implementation of `mod(float x, float y)` may be useful in some cases

$$\frac{y}2 - \frac{y}{\pi} \arctan \left ( \cot \left( \frac{x}y\pi \right) \right)$$

https://www.desmos.com/calculator/2uczus4jyr
> -1 votes

---
Tags: arithmetic, floating-point, integers
---


title: What is it called when f(g(x)) = x?

text:
# Question
Title: What is it called when f(g(x)) = x?
There are a couple of function pairs which give the identity when composed, e.g.,

* `decrypt(encrypt(value)) == value`
* `deserialize(serialize(data, filepath)) == data`

What is this property called? Suppose one function undoes the property of the other, and it is guaranteed that this is possible for all values (within the domain of interest).

# Answer
> 18 votes
I would add to the existing answer that the composition $h = f \circ g$ is the identity, which you already pointed out. This means that $g$ is the right-inverse of $f$, and $f$ is the left-inverse of $g$. That makes each of $f$ and $g$ *invertible* on the given side. For the pairs you have given, I would expect $g \circ f$ to also be the identity in the naïve/straightforward case, and so the left/rightness is flipped, and you have full inversion. The domain matters, as usual.

As pointed out in the comments, this is not necessarily the case for some kinds of the functions you give—re-encrypting after retrieving the original value $(g \circ f \circ g)(x)$ may not necessarily give the same encrypted code $g(x)$; but then, it’s not nearly useful to consider $g$ a function, for the normal rules don’t apply. Notice that we still take the value passed to $f$ (here, the decryptor) to be an encrypted value; we assume the domain of $f$ to be properly encrypted values. Mathematically we are unable to apply $f$ to anything else (though I could have used a name like $y = g(x)$). Programmatically, of course, the type system *may* permit values outside the domain to be given, and then we either get an error or garbage. Again, I consider those irrelevant and outside the domain here.

Versioned serialization actually doesn’t have this issue—a function that deserializes or serializes a different version than $f$ or $g$ is *not* $f$ or $g$, respectively, and therefore not relevant! **The domain matters.**

We also have $\forall x$ in the domain $h(x) = x$ by definition, and that means every $x$ is a fix-point of $h$ (this is trivially true for any identity).

# Answer
> 11 votes
The language borrowed from category theory is that `f` is a *retraction* of `g`, and `g` is a *section* of `f`.

If `f` is both a retraction and a section of `g`, then it's called an *inversion*.

# Answer
> 1 votes
decrypt is the **inverse** of encrypt

deserialize is the **inverse** of serialize

In other words, the composition of a function and its inverse are the identity function.

# Answer
> -1 votes
If for all $x$ in some set $S$, we have $f(g(x)) = x$ then $f$ is the "***inverse***" of $g$

---
Tags: terminology
---


# Question
Title: What is the meaning of this error message I get when downloading documents?
Every so often I'll hop on my laptop, open google, and eventually try to download and open some document, only for the document to wind up looking like this:

What on earth does all this mean? What language is it, and why does it pop up instead of normally formatted English?

Also, if it isn't already obvious, I have zero technical experience with software and have no idea what sort of jargon I would use to even ask this question properly. Please keep in mind that I'm just a schlub who wants to know what this means.

# Answer
Usually, that type of corrupt rendering is caused by trying to open a document in software it wasn't meant for. For instance, if you try to open a Word document (.doc) in Notepad, you'll often get something like that.

If you got this document from the internet, it's probably a pdf. Adobe Acrobat Reader is your best bet for reading this type of document. If your computer doesn't come preinstalled with it, you can download it for free from here.

If it isn't a pdf, you might need other software.
> 0 votes

---
Tags: computer-networks
---


# Question
Title: How does the cache / memory know where to return results of read requests to?
The pipeline of a modern processor has many stages that may issue read requests to main memory, e.g. in fetching the next command or loading some memory location into a register. How is the result of a read request returned to the right pipeline stage, given that there are more than one possible recipients? Since most CPUs access main memory via a cache hierarchy, the question becomes: how does the L1 cache know which part of the pipeline to return a result to?

I imagine that access to the L1 cache is queued, but each access presumably needs a 'return address'. How is this typically handled?

Processors tend to have a LSU (= load-store unit), see \[1, 2\] for example, but those descriptions tend not to mention how read data finds its recipient.

---

1. RISC-V Boom, The Load/Store Unit (LSU).
2. Arm, Load Store Unit (LSU).

# Answer
> 2 votes
Every machine instruction encodes the source and destination registers and/or memory locations. For memory location, some temporary buffer (register) within the processor is used. If the memory location happened to be in the cache, the stage of pipeline which depends on the content of memory location, stalls for few cycles.

Also, there are buffer registers between every pipeline stage, that stores the input for next stage and output of previous stage. If the processor is superscalar, i.e., multiple instructions can be in flight at a certain point of time, then multiple copies of buffers are maintained. Since the instruction can be executed Out-of-Order on superscalar processors, buffers like ROB (re-order buffers) are maintained for every hardware (SMT) threads. Put simply, multiple register sets which are copies of processor register sets are maintained within a processor.

In other words, Control unit that control the instruction execution cycles, appropriately route the content of memory location to marked registers. Registers are either specified by instruction code or determined by control unit itself.

---
Tags: computer-architecture, cpu-cache, memory-access
---


# Question
Title: Is address bus size same as physical address size and is that the same as word size?
I am having some confusion between address bus size, physical address size and word size however (I do understand that unit of memory access is word and when word size is one byte then it's known as byte-addressable).

# Answer
> 0 votes
> Is address bus size same as physical address size

No, not necessarily. Especially with modern 64 bit address bus sizes, it is quite common that CPUs do not actually support 64 bit physical addresses.

For example, the first AMD64 CPUs had 40 bit physical addresses, the current ones have 48 bit. In fact, due to the Page Table Entry format, physical addresses cannot be larger than 52 bit.

> and is that the same as word size?

No, not necessarily. It makes stuff easier, but there have been architectures where the bus was half the word size, and you had to transmit a word in two bus cycles. Conversely, it is also possible to have the bus width be an integer multiple of the word size, making it possible to transmit multiple words per bus cycle.

Just as an example: the IBM 704, one of the most famous computers of all time (both FORTRAN and LISP were first implemented for the IBM 704, the trajectory data for Gemini and Apollo was computed on one) has 36 bit words but 15 bit addresses.

---
Tags: cpu, memory-hardware, cache
---


# Question
Title: Gradient descent overshoot - why does it diverge?
I'm thinking about gradient descent, but I don't get it.
I understand that it can overshoot the minimum when the learning rate is too large. But I can't understand why it would diverge.
Let's say we have

$$J(\theta\_0, \theta\_1) = \frac{1}{2m}\sum\_{i=1}^m (h\_\theta(x^i)-y^i)^2$$

$$\theta\_1 := \theta\_1-\alpha\frac{\partial}{\partial\theta\_1}J(\theta\_1)$$

When the slope is negative the cost will converge to the minimum from the left of the graph, as $\theta\_1$ will increase.
When the slope is positive it will converge from the right of the graph, as $\theta\_1$ will decrease.
Now it might overshoot when the learning rate $\alpha$ is too large.
In that case it should overshoot again.
But not by much, should it not circle around the minimum? Why would it diverge?

# Answer
> 4 votes
I think it's useful to understand first why gradient descent *converges*. We assume that our function has $L$-Lipshitz gradient:

$$\\|\nabla f(x) - \nabla f(y)\\| \le L \\|x - y\\|,$$

or, in 1-dimensional case:

$$|f'(x) - f'(y)| \le L |x-y|$$

The main tool in non-convex optimization is the **Descent Lemma**: $$f(y) \le f(x) + \langle \nabla f(x), y - x \rangle + \frac L2 \\|y - x\\|^2$$ or, in 1-dimensional case: $$f(y) \le f(x) + f'(x) (y - x) + \frac L2 (y - x)^2$$ (Descent Lemma makes an intuitive sense because of Taylor expantion and since $L$ is an upper bound on $|f''(x)|$ by Mean-Value theorem applied to $f'$)

Now, let's make a gradient descent step: $y \gets x - \gamma \nabla f(x)$. Substituting this into descent Lemma, we have:

\begin{align} f(y) &\le f(x) + \langle \nabla f(x), -\gamma \nabla f(x) \rangle + \frac L2 \\|\gamma \nabla f(x)\\|^2 \\ &= f(x) - \gamma \\|\nabla f(x)\\|^2 + \frac {L \gamma^2}2 \\|\nabla f(x)\\|^2 \\ &= f(x) - \gamma(1 - \frac {L \gamma} 2) \\|\nabla f(x)\\|^2 \end{align}

Therefore, when $\gamma \le \frac 2L$, we have $f(y) \le f(x)$. Something like $\gamma = \frac 1L$ suffices for convergence of canonical gradient descent.

**But** what if $\gamma \> \frac 2L$? The thing is, there are cases when Descent Lemma is tight: for example, when $f$ is quadratic. Let $f(x) = x^2$. It has $f'(x) = 2x$ and $L=2$ (since $|2x - 2y| \le 2 |x-y|$). Then, by selecting $\gamma \> \frac 2L = 1$, we have:

$$(x - \gamma 2 x)^2 = (2 \gamma - 1)^2 x^2 \> (2 - 1)^2 x^2 \> x^2,$$

I.e. gradient descent diverges.

# Answer
> 1 votes
If you overshoot by 10% you are fine, for example if the solution is 0 and the starting value 1000, you go to -100, +10, -1, +0.1 etc. If you overshoot by 80%, you converge but much smaller. If you overshoot by 110% you go from 1,000 to -1,100, +1,210, -1,331 etc. - divergence.

---
Tags: optimization, machine-learning, gradient-descent
---


title: Halting problem theory vs. practice

text:
# Question
Title: Halting problem theory vs. practice
It is often asserted that the halting problem is undecidable. And proving it is indeed trivial.

But that only applies to an arbitrary program.

Has there been any study regarding classes of programs humans usually make?

It can sometimes be easy to analyze a program and enumerate all of its degrees of freedom and conclude that it will halt.

For example, has there ever been an effort to create a programming language (scripting really) that guarantees halting? It would not be widely applicable but could still be useful for mission critical modules.

# Answer
Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of its variants for instance. It's common for the soundness of a type system to boil down to proving that all programs normalize in it. Strong normalization is a very desirable property in general in programming languages research.

I haven't seen a lot of success in catching infinite loops in practice however "Ensuring Termination in ESFP" by Telford and Turner shows a more robust termination checker that was able to prove that Euclid's algorithm always terminated and handles partial cases. Euclid's algorithm is a famously tricky example of a primitive recursive function that isn't straightforwardly provable to be primitive recursive. It fails checkers that simply look for a decreasing parameter (or some simple pattern of decreasing parameters like Foetus termination checker). To implement this using primitive recursive combinators you have to encode a proof of termination for the algorithm as a parameter in the function essentially.

I can't think of any results for procedural languages off the top of my head and most results in functional languages use some kind of restriction that makes the obviously terminate rather than trying to perform some kind of complex analysis to ensure that more natural programs terminate.
> 20 votes

# Answer
There is past and current research on this. Such problem is called Termination Analysis, and a quick look on Google (Scholar) provides several old as well as new publications on this:

1. 2005, *Termination Analysis of Higher-Order Functional Programs*;
2. 2006, *Automated Termination Analysis for Haskell*;
3. 2008, *Termination Analysis of Logic Programs based on Dependency Graphs*;
4. 2010, *Loop summarization and termination analysis*;
5. 2014, *Termination Analysis by Learning Terminating Programs*;
6. 2015, *Termination analysis with recursive calling graphs*;
7. 2019, *Static Termination Analysis for Event-driven Distributed Algorithms*;
8. 2019, *Implementing termination analysis on quantum programming*;

Including existing languages with in-built mechanisms for that such as:
> 2 votes

# Answer
Microsoft has developed a practical code checker (whose name escapes me at the moment) which performs halt-testing. It exploits the fact that the code it checks is human-written and not arbitrary, just as you suggest. More importantly, it bypasses the impossibility proof by being allowed to return the answer 'Cannot decide' if it runs into code too difficult to check.
> 1 votes

# Answer
There are only 2 types of infinite programs:

1. Those that **repeat their own state** after a point (cyclical)
2. Those that **grow indefinitely** in used memory

Those in 1st type, follow this pattern:

Where there is a pair of distinct indices i and j such that xi = xj, and after which the cycle repeats itself again (thanks to the deterministic nature of programs). In this case the inputs x, contain the whole memory and variables used by the algorithm, plus the current instruction pointer.

Cycle detection algorithms work very well in practice for this type and can prove that a given cyclical program will never finish, usually after a small number of steps, for most random programs.

Proving those in the **2nd type is where the challenge is**. One could argue that type 2 can never exist in reality (as all computers have finite memory) but that is not very useful in practice because the memory used may grow very slowly for a regular computer to ever be full. A simple example of that is a binary counter that never stops and never repeats its full state completely.
> 1 votes

# Answer
There is a huge class of functions that are trivially guaranteed to halt: Everything with a finite number of loops, with an upper limit for the number of iterations for each loop determined before the loop is started.

If you have a random program, it can be difficult to prove whether or not it halts. Programs that are written for a purpose are usually much easier.
> 0 votes

# Answer
The smart contracts functions in the Ethereum blockchain are an example of a system that needs the guarantee of halting, not to stall the whole chain.

Every function has a gas cost, and the gas cost translates into real Ethereum coins. A transaction fee must be paid to call the contract. If the gas used in the contract exceed the gas paid with the transaction fee, the computation terminates immediately.
> 0 votes

---
Tags: computability, programming-languages, undecidability, halting-problem
---


title: Container with findNthSmallest in O(1)

text:
# Question
Title: Container with findNthSmallest in O(1)
> Consider the following problem: we want to implement ADT SpecialContainer which stores integer numbers and is similar to a PriorityQueue. This container should support the following operations:
>
> * `init(sc, n)` \- create a new, empty SpecialContainer `sc`. `n` is a positive integer number (will be used later) - $\Theta(1)$ total complexity
> * `push(sc, x)` \- adds the integer number `x` to the SpecialContainer - $O(\log n)$ total complexity
> * `findNthSmallest(sc)` \- returns the `n`th smallest element from `sc`, where `n` is the number given to the init function - $\Theta(1)$ total complexity
> * `popNthSmallest(sc)` \- removes and returns the `n`th smallest element from sc - $O(\log n)$ total complexity
>
> 1. Which data structure or combination of data structures would you use as representation for the SpecialContainer and how?
> 2. Explain in short how would you implement each operation of the SpecialContainer and why the implementation fits the complexity requirement.

I was thinking about a combination of a heap and a hash map, but I don't think if it works. Can somebody help me, please?

# Answer
> 0 votes
As pointed out by orlp, it's impossible to do in $O(\log n)$ time. However, we can do this in $O(\log N)$ time, where $N$ is the total number of items.

You can do this with 2 Heaps: The first heap is a max-heap with the smallest $n$ elements. Its root is the $n$-th smallest element. The second one is the min-heap with the rest of the elements. Its root is the $n+1$-th smallest element.

When max-heap has less than $n$ elements, the operations are trivial. Otherwise:

* findNthSmallest() - it's just the root of the max-heap. O(1) time
* popNthSmallest():
    1. Pop the root of the max-heap
    2. x := Pop the root of the min-heap
    3. Insert x into the max-heap
* push(x):
    1. Push x into the max-heap
    2. y := Pop the root of the max-heap.
    3. Push y into the min-heap.

---
Tags: data-structures
---


# Question
Title: NP-Complete Problem and Polynomial Hierarchy
I have tried to search the internet to check if the following is correct: If $\sum\_{2}$ contains a NP-Complete problem then PH collapses to NP: $PH=NP$

For example if $SAT\epsilon\sum\_{2}$ than: $PH=NP$

# Answer
$\mathrm{SAT}$ and all $\mathrm{NP}$-complete problems are certainly in $\Sigma\_2^P$, as $\mathrm{NP} \subseteq \Sigma\_2^p$. It is true however that if $\mathrm{SAT}$ (or any $\mathrm{NP}$-complete problem) ever gets proven to be $\Sigma\_2^p$-hard, then $\mathrm{NP} = \Sigma\_2^p$, and consequently the polynomial hierarchy collapses to $\mathrm{NP}$.
> 2 votes

---
Tags: np-complete, satisfiability
---


# Question
Title: Algorithm for Estimating Number of Unique Monthly Visitors
Is there a way to estimate the number of unique monthly visitors to a site based on a limited sample of one week of data? I have information about when a given user visited the site. This isn't as simple as just multiplying the number of unique visitors the first week by 4, due to the hotel problem. If 10 people visit your site the first week and the same people are the only visitors to your site the second, third, and fourth week, the total number of monthly unique visitors to your site is only 10.

I know you can use HLL to estimate the number of unique visitors to a site in O(1) space. I'm wondering if there's a similar approach to estimate how many unique visitors there will be after a month, preferably that also works in O(1) space.

# Answer
After digging into this for a bit, I came across this paper which provides a solution. The paper gives an approach to estimating the number of new species that will be observed given an initial sampling period. It models observing a given species as a Poisson distribution. It gives the following estimator for the number of new species that will be discovered:

$$ \hat{\Psi}(t)=\sum\_{k=1}^{k\_{m a x}} N\_{k} e^{-k}-\sum\_{k=1}^{k\_{m a x}} N\_{k} e^{-k(1+t)} $$

where $N\_{k}$ is the number of species that were observed $k$ times and $t$ is the length of the second sample relative to the initial sample.
> 0 votes

# Answer
Not without making assumptions. You can't tell the difference between a site with a $N$ users who visit once a week (on a random day of the week), vs a site with $4N$ users who visit once a month (on a random day of the month).
> -1 votes

---
Tags: algorithms, data-structures, statistics
---


# Question
Title: Fast query on the number of elements in a quarter plane
I have a scatter of 2D elements on a 2D plane.

I would like an efficient algorithm to prepare and query the number of points in a quarter plane (inclusive of boundary).

The quarter plane is defined by a point $(x,y)$. All elements $(x', y')$ where $x\<=x'$ and $y\<=y'$ are in the quarter plane.

For example

* I have elements `[(1,1), (2,2), (1,2), (3,2)]`,
* My queries are `[(1,1), (2,2), (3,3)]`

The program should return `[1,3,4]`.

This is for a past competitive programming challenge (WiFi Network problem in this competition)

# Answer
> 1 votes
A 2D Fenwick tree can solve this in $O(\log^2 N)$ time and $O(N^2)$ space for both update and query, when your coordinates are integers and $N$ is the size of the maximum coordinate.

Fenwick trees are nice for competitive programming because they have a really compact implementation, for example in C++:

```
typedef unsigned long long uw;
uw lsb(uw x) { return x & -x; }
uw  up(uw x) { return x + lsb(x); }
uw  dn(uw x) { return x - lsb(x); }

template<class T> struct Fenwick2D {
  uw n; std::vector<std::vector<T>> b;
  Fenwick2D(uw n) : n(n), b(n+1, std::vector<T>(n+1)) { }

  void increase(uw x, uw y_, T v) {
    for (; x <= n; x = up(x))
      for (uw y = y_; y <= n; y = up(y))
        b[x][y] += v;
  }

  T prefix_sum(uw x, uw y_) {
    T s = 0;
    for (; x >= 1; x = dn(x))
      for (uw y = y_; y >= 1; y = dn(y))
        s += b[x][y];
    return s;
  }
};

```

And this shows your example from the question:

```
int main(int argc, char** argv) {
    Fenwick2D<int> fw(4);
    fw.increase(1, 1, 1);
    fw.increase(2, 2, 1);
    fw.increase(1, 2, 1);
    fw.increase(3, 2, 1);
    std::cout << fw.prefix_sum(1, 1) << "\n";
    std::cout << fw.prefix_sum(2, 2) << "\n";
    std::cout << fw.prefix_sum(3, 3) << "\n";
    return 0;
}

```

This data structure is more general than your problem as well. In general it can increase any grid element $g\_{x,y}$ by value $v$ (which decreases for negative $v$), and ask the value of the lower quadrant prefix sum $\sum\_{i\leq x}\sum\_{j\leq y} g\_{i,j}$ for any $x, y$. Note that this means you can get area sums as well using 4 queries by the inclusion-exclusion principle.

---
Tags: algorithms
---


# Question
Title: Question about the CLRS Linear Programming chapter
I'm currently reading the CLRS Linear Programming chapter and there is something i don't understand.

The goal is to prove that given a basic set of variables, the associated slack form is unique

They first prove a lemma :

And then they prove the result :

My concern is that to prove the second lemma, they apply the first lemma. However equations (29.79) -\> (29.82) only holds for feasable solutions, which is not for any x, so why can they apply the first lemma ?

# Answer
Lemma 29.4 mentions an LP, because that is what they need it for, but it is really a statement in linear algebra about the system of equations $Ax=b$ and a linear form $\phi(x)=c\cdot x$, which in the LP is the objective function.

> **Lemma 29.4:**
>
> If the variables $x\_i,i\in B$ are basic variables, i.e. if the corresponding columns of $A$ are a maximal set of linearly independent columns, then you can solve for those variables in terms of the rest of the variables $x\_i,i\in N$ and the polynomials obtained are unique. In addition, if you write $\phi(x)=\psi(x\_i,i\in N)$, the polynomial $\psi$ is also unique.

(Well, this version of the lemma includes the assertion that one can solve for those variables. This is due to Gaussian elimination.)

Now, for the uniqueness, as they did, you assume that you have two expressions of the basic variables in terms of the non-basic ones

$(x\_i)\_{i\in B}=(b\_i)\_{i\in B}+S(x\_j)\_{j\in N}$ for some matrix $S$ and $(x\_i)\_{i\in B}=(b\_i')\_{i\in B}+S'(x\_j)\_{j\in N}$.

So the polynomials $(b\_i)\_{i\in B}+S(x\_j)\_{j\in N}$ and $(b\_i')\_{i\in B}+S'(x\_j)\_{j\in N}$ are the same.

By definition $(b\_i)\_{i\in B}=(b\_i')\_{i\in B}$ and $S=S'$.

There is no real need to talk about values of the variables, since all the statements are purely algebraic, in the ring of polynomials in the variables $x\_i$. So, there is no need for Lemma 29.3. Of course, the equations written have to be thought as equations between polynomials and not as equations between values of functions that are satisfied for all values of the variables. Ignore this paragraph if it causes confusion.
> 2 votes

---
Tags: linear-programming
---


# Question
Title: Bresenham's line drawing algorithm guarantees
I am considering implementing my own version of Bresenham's line drawing algorithm, found here, my one question is does the algorithm guarantee that both endpoints will be covered/drawn. I am doubting this because of the error accumulation factor (decision variable), but I may be wrong.

# Answer
Yes, Bresenham line drawing algorithm guarantees that endpoints are drawn.

The error accumulation is used for drawing and decreased after drawing a pixel, this is the core idea of the algorithm: incremental error is accumulated to avoid division operation, which is costly, but in this context it is something good and it doesn't mean that errors would damage continuity of line or lose endpoints.

The failure of Bresenham algorithm is technically possible only if floating point variable fails to add error, so $$deltaerr := abs(deltay / deltax)$$ is so small that $error := error + deltaerr$ would not increase $error$ at all, but if that happened, image is too big to fit on computer or some kind of clipping algorithm or bigger floating point variables are needed.

It is safe to assume that $\frac{deltay}{deltax} \le \frac{1}{2^{22}}$ is not going to happen.
> 2 votes

---
Tags: graphics, computer-graphics
---


# Question
Title: How hard would it be to state P vs. NP in a proof assistant?
GJ Woeginger lists 116 invalid proofs of P vs. NP problem. Scott Aaronson published "Eight Signs A Claimed P≠NP Proof Is Wrong" to reduce hype each time someone attempts to settle P vs. NP. Some researchers even refuse to proof-read papers settling the "P versus NP" question.

I have 3 related questions:

1. Why are people not using proof assistants that could verify whether a proof of P vs. NP is correct?
2. How hard or how much effort would it be to state P vs. NP in a proof assistant in the first place?
3. Is there currently any software that would be at least in principle capable of verifying a P vs. NP proof?

# Answer
> 23 votes
I'm going to disagree with DW. I think that it is possible (although difficult) for a P vs. NP result to be stated in a proof assistant, and moreover, I wouldn't trust any supposed proofs unless they were formalized in this way, unless they came from *very* reputable sources.

In particular, none of the resources DW states are based on type theory, which is a very promising direction for proof assistants. Coq has been used to formalize the proof of the 4-color theorem among others, so it's clearly capable of some heavy mathematical lifting.

To answer your specific questions:

1. The main reason is that theorem provers aren't widely accepted in the mathematical community. Learning them takes effort, and mathematicians are often skeptical of the underlying techniques (type theory, constructive math, etc.) But there are some fields where leading researchers are very comfortable with making large developments formalized in a proof assistant, like category theory, programming language theory, formal logic, etc. So I think there is as much of a cultural issue as an inherent feasibility issue.

The other reason is that, so far, most of the purported "proofs" have been by cranks, who don't want to formalize their result because it will inevitably reveal the flaws.
2. It is not hard at all to state P vs. NP in a proof assistant. One could use Turing Machines, but it would probably be easier to model a simple Turing-complete programming language using inductive families to model small-step semantics, and define the run-time as the number of steps a program takes. You could define $P$ as the languages accepted by programs halting in a polynomial number of steps, and $NP$ as languages that can be verified in polytime with a polynomial-length certificate.

EDIT: It turns out there are existing techniques for showing that algorithms run in polynomial time in a theorem prover. So this could be used either to show a polytime algorithm for an NP-hard problem, or to derive a contradiction from the existence of such an algorithm.
3. There is *tons* of software that is capable of verifying such a proof, *provided the proof was written using that software*. The two candidates I'd put the most stock in are Coq and Lean. Coq in particular has been used to verify several major results in mathematics.

# Answer
> 10 votes
Using proof assistants for this purpose is certainly possible in principle, but I suspect it would take more effort than most folks who write such proofs would be interested in putting in. It would require a substantial amount of effort from the author of a purported P vs NP proof to formalize their proof.

Translating a proof written for humans into a format that a proof assistant can verify was tedious and time-consuming. I have seen estimates of between a day to a week of effort per page of human-written proof. Then, one must also formalize all prior results that the proof is building on. When we look at recent attempts at proving P vs NP, they typically use a lot of advanced machinery and sophisticated pre-existing results from prior papers, which would need to be formalized too.

Because of this, I expect it would be completely impractical to formalize both the proposed new proof and the proofs of all prior results that it relies upon, for the kinds of purported proofs we've seen so far. As user21820 points out, what would be more practical would be to formalize only the statement of all prior results that are relied upon, but not their proof. Thus, instead of proving the theorem $T$, we'd formalize a proof that $(X \land Y \land \cdots) \implies T$, where $X,Y,\dots$ are the prior results that the proof relies upon. This falls short of fully verifying the NP-completeness result, but if people have faith in the prior results, it would allow people to gain confidence in the new result. This would be a lot more realistic than formalizing the entire proof of $T$: while it would take some effort to formalize all of the prior results $X,Y,\dots$, it's a lot less than the effort to formalize the proofs of those prior results too.

Still, it would be challenging and require a non-trivial expenditure of effort to formalize a proof, even with this trick.

You can look at existing libraries of theorems in mathematics and computer science that have been formalized and formally verified: see http://us.metamath.org/ and http://formalmath.org/ and https://www.isa-afp.org/topics.html and http://mizar.org/library/. You might notice that a lot of what is formalized there concerns basic undergraduate material. We're a far way from formalizing all theorems taught at an undergraduate level, let alone those taught at a graduate level, let alone new research results.

For more background, see https://math.stackexchange.com/q/792010/14578 and https://math.stackexchange.com/q/113316/14578 and https://math.stackexchange.com/q/1767070/14578 and https://math.stackexchange.com/q/2747661/14578 and http://www.ams.org/notices/200811/tx081101370p.pdf.

# Answer
> 9 votes
I can give a direct answer to (2): $P\ne NP$ has been stated in Lean (along with the other main results of Cook's paper, where the conjecture was first described), as part of the Formal Abstracts project.

# Answer
> 4 votes
I believe your question is not that much of a proper theory question, so with your permission I'll give it a not-so-technical answer.

> Why are people not using proof assistants that could verify whether a proof of P vs. NP is correct?

Because CS theorists rarely (perhaps extremely rarely) write proofs in machine-verifiable form.

> How hard or how much effort would it be to state P vs. NP in a proof assistant in the first place?

Very hard at least in the "uninteresting" sense that @DW explained; but it could be anywhere from easy to impossible in the "interesting" sense of expressing the concepts in a proof, if it were to exist.

But you know, this will never happen because:

1. Until a proof is found it can't be done anyway
2. You have to know the proof like the back of your hand to convert it into machine-verifiable form.
3. ... and when enough people know the proof, they will either have found a flaw or be satisfied that it's valid and not care about machine-checking it.

> Is there currently any software that would be at least in principle capable of verifying a P vs. NP proof?

I'm not well-versed enough in proof verification software to comment about what's actually implemented, but it's probably nearly-impossible to answer your question, because - who knows what form such a proof will take? And thus - how would you know, now, if it's expressible in such a way that your proof verifier can process?

---
Tags: complexity-theory, p-vs-np, proof-assistants
---


# Question
Title: Tried to derive the Z combinator and instead derived another
I was working to derive the Z-Combinator by starting with the factorial function and ended up deriving a different fixed-point combinator. What did I derive? Did I make a subtle mistake?

Here are the steps I performed (in JavaScript)

## 1. Declare factorial function

```
let fact = n =>
    n < 2 ? 1 : n * fact(n - 1)

```

## 2. Convert to combinator (closed expression)

```
let fact = (self, n) =>
    n < 2 ? 1 : n * self(n - 1)

```

## 3. Thread self call

Based on signature `fact(?, 7)`, passing `fact` as first argument seems reasonable `fact(fact,7)`. So thread the parameter through the tail call:

```
let fact = (self, n) =>
    n < 2 ? 1 : n * self(self, n - 1)

```

Usage is now `fact(fact,7)``5040`

## 4. Refactor to curried form

```
let fact = self =>
    n => n < 2 ? 1 : n * self(self)(n - 1)

```

## 5. Move self application to local declaration

```
let fact = self => {
    let f = n => self(self)(n)
    return n => n < 2 ? 1 : n * f(n - 1)
}

```

## 6. Convert let declaration to lambda expression

```
let fact = self =>
    (f =>
        n => n < 2 ? 1 : n * f(n - 1)
    )(
        n => self(self)(n)
    )

```

Usage is still `fact(fact)(7)``5040`

## 7. Separate the factorial expression

```
let _fact = f => n =>
    n < 2 ? 1 : n * f(n - 1)

let fact = self =>
    (
        _fact
    )(
        n => self(self)(n)
    )

```

## 8. Move self-application from caller to body

```
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact = (() => {
    let innerFact = self =>
        (
            _fact
        )(
            n => self(self)(n)
        )
    return innerFact(innerFact)
})()

```

Usage is now `fact(7)``5040`

## 9. Convert let declaration to lambda expression

```
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact = (() => {
    return (
        innerFact => innerFact(innerFact)
    )(
        self => (_fact)(n => self(self)(n))
    )
})()

```

## 10. Simplify expression

```
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact =
    (innerFact => innerFact(innerFact))
    (self => (_fact)(n => self(self)(n)))

```

Sanity check. Usage is still `fact(7)``5040`

## 11. Rename variables

The usage of `innerFact` and `self` look suspiciously similar. Rename to the same variable to discover a pattern. Separate lexical scopes so safe to do:

```
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact =
    (u => u(u))
    (u => (_fact)(n => u(u)(n)))

```

## 12. Abstract `_fact` usage and rename `fact`

Rename `fact` to `setup` and abstract `_fact` in body by replacing with parameter `f`

```
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

let fact = setup(_fact)

```

No need for separate `_fact` declaration so inline:

```
let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

let fact = setup(
    f => n => n < 2 ? 1 : n * f(n - 1)
)

```

## 13. Rename `setup`

Rename it to what? What combinator is this? According to Wikipedia The Z combinator is:

```
let Z = f =>
    (u => f(v => u(u)(v)))
    (u => f(v => u(u)(v)))

```

But what I've derived is:

```
let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

```

Defining `fact` in terms of either seems equivalent in behavior. Did I make a mistake? Did I accidentally rediscover another well-known combinator?

# Answer
If I inline `(u => (f)(n => u(u)(n)))` into `(u => u(u))` I get:

```
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))

```

Which is exactly the Z-Combinator.

From wikipedia:

```
let Z = f =>
    (u => f(v => u(u)(v)))
    (u => f(v => u(u)(v)))

```

My derivation:

```
let fix = f =>
    (u => f(n => u(u)(n)))
    (u => f(n => u(u)(n)))

```
> 0 votes

---
Tags: lambda-calculus, combinatory-logic
---


# Question
Title: Undecidability of the language of all Turing Machines with repeat strings as their language
Show that the language consisting of all Turing machines whose language consists of strings that can be broken up into two consecutive and equal strings is undecidable.

I would prefer if reduction was used and not Rice's theorem.

# Answer
> 1 votes
Imagine a fixed machine $M$ and a fixed string $w$ and then let $M'$ be the machine that on input $x$ simulates $M$ on $w$, and if that simulation halts then answers Yes if $x=ab$ and No otherwise.

How could you decide whether $M'$ belongs to your language? You would need to know whether $M$ halts on $w$! As in that case $L(M')=\\{ab\\}$ and otherwise $L(M')= \varnothing$.

Details up to you :)

---
Tags: undecidability
---


# Question
Title: Universality of $(+, \oplus)$ over $\mathbb{Z}_2^n$
Let $\mathbb{Z}\_2^n$ be the field of bitvectors of length $n$ and define the xor operator $\oplus$ and the addition operator $+$ over this field, with $+$ having the usual overflow semantics (take addition modulo $2^n$).

Is it possible to express any mapping $f: \mathbb{Z}\_2^n \rightarrow \mathbb{Z}\_2^n$ entirely in terms of $\oplus$ and $+$? It seems like it might be possible due to the nonlinearity of $+$.

---

For instance, if we were given $n=2$ and that $f(0) = 3, f(1) = 1, f(2) = 3, f(3) = 1$, then we could construct $f$ as $f(x) = x\oplus(x+3)$.

# Answer
Nope. For instance, you can't express the function $f(x)=x\>\>1$. In general, the least-significant bit of $f(x)$ depends only on the least-significant bit of $x$. You can prove that by structural induction, using the following two properties: $(a \oplus b) \bmod 2 = (a \bmod 2) \oplus (b \bmod 2)$ and $(a + b) \bmod 2 = (a \bmod 2) + (b \bmod 2) \bmod 2$.
> 2 votes

---
Tags: boolean-algebra
---


# Question
Title: Looking for memory-efficient way to detect hash collisions
Given a hash function H, it's possible that H(a) = H(b) = c

Let's assume we have a big data set \[N1 ... Nk\], with K items and we hash each item in this set

After operation is done, we'd get a set of hashes \[H1 ... Hm\] where m \< k, meaning we had collisions

What would be the most memory-efficient way(without storing all of hashes and hashed items) to determine if we've ever hashed item X before and if we did, did it collide with anything?

Is it even possible to relax memory constrains on such kind of task?

# Answer
> 2 votes
Assume you have a good hash function producing an n bit hash code, that is $2^n$ possible values. Assume you are hashing k values, so there are about $k^2/2$ pairs of hash codes that might collide. The probability of a collision is about $k^2 / 2^{n+1}$.

By picking a large n, you can make that probability arbitrarily small. Ask a physicist to calculate the probability that your computer will be hit by a meteor and completely destroyed, together with all hash values. Pick n large enough that the probability of a collission is say 1,000 times smaller than the probability of a total destruction of the computer involved.

You might also consider what is the amount of damage if you have a collission. For example, the damage could be that as a result, there will be one person in the world who can enter your country with the passport of one specific other person. Make n large enough so that the expect damage through a collision is negligible.

(That's the principle behind the use of GUIDs. There is no guarantee that there are no collisions, but with a proper implementation the probability can be neglected. )

# Answer
> 1 votes
If you go and change your hash function, you'll have to apply *all* the ones in the history for following elements (to see if one repeats). The cost of doing that is larger than just handling collisions some way.

Why do you impose this rather strange requirement? If you know the elements beforehand, you can cook up a hash function with no colissions and not too large of a range of the function, but it is quite costly...

---
Tags: hash
---


# Question
Title: Odd cycle transversal and linear programming
Suppose we have a graph $G$ with $n$ vertices. Suppose *LP* is a linear programming problem where there is a variable for each vertex of $G$, each variable can take value $≥0$, for each odd cycle of $G$ we add to *LP* the constraint $x\_a+x\_b+x\_c+\dots +x\_i≥1$ where $x\_a,x\_b,x\_c,...,x\_i$ are the vertices of the cycle. The objective function of *LP* is $\min \sum\limits\_{1}^{n}{x\_i}$.

Suppose $S$ is an optimal solution of *LP*. If a variable $x\_v$ takes on a value $\>0$ in $S$, is it guaranteed that there exists a minimum odd cycle transversal that contains $v$? By minimum odd cycle transversal, I mean an odd cycle transversal with the fewest number of vertices.

# Answer
> 1 votes
No, $v$ does not have to belong to any minimum odd cycle transversal.

Consider the following undirected graph. The vertices are split into eight groups: $C\_i$ for $i \in \[0, 3\]$, each of them containing $4$ vertices and $F\_i$ for $i \in \[0, 3\]$, each containing $3$ vertices. The following edges (and only them) are present in the graph:

1. All edges between $C\_i$ and $C\_{(i + 1) \bmod 4}$ for every $i \in \[0, 3\]$
2. All edges between $C\_i$ and $F\_i$ for every $i \in \[0, 3\]$
3. All edges between $F\_0$ and $F\_2$, all edges between $F\_1$ and $F\_3$

Let's prove the following statements:

1. Any OCT that contains a vertex from one of the $C\_i$'s has size at least $7$, but there are OCT's of size $6$ (for example, $F\_0 \cup F\_1$).
2. In any optimal solution to the LP relaxation, the variables corresponding to vertices from $F\_i$'s are set to zero. Moreover, there is only one optimal solution to the LP relaxation: set all variables corresponding to vertices of $C\_i$ to $1/3$.

If both are true, then, for *every* nonzero variable in the optimal solution to the LP, there is no minimal OCT that passes through the corresponding vertex. Because the graph is small enough, you can verify both these statements on a computer. But I will give a short "human" proof to both.

For the minimum OCT part, it is clear that we should either delete each of the vertex group either fully, or not touch it at all (because just a single vertex from the group is "good enough representative" for the whole group). Moreover, we can see that deleting one $C\_i$ group is not enough. If we delete, say, the group $C\_0$, there is still an odd cyle $F\_1 \to C\_1 \to C\_2 \to C\_3 \to F\_3 \to F\_1$. Hence, we still have to delete at least one other group, for $7$ vertices in total. On the other hand, $F\_0 \cup F\_1$ is an OCT with size $6$.

Now let's deal with LP part. It can be seen that all odd cycles in the graph pass through at least $3$ vertices from $C\_i$. Hence, assigning weight $1/3$ to each vertex of each $C\_i$ yields a solution with total cost $16/3$. On the other hand, consider all cycles of length $5$ in our graph. It can be proven that all vertices from $C\_i$'s lie on exactly $3/16$ fraction of them, but all vertices from $F\_i$'s lie on exactly $1/6$ fraction of them (the proof is a bit tedious to write down, so I will add it only by request). Then, by averaging the inequalities $x\_a + x\_b + \ldots + x\_\ell \geqslant 1$ over all these cycles, we get $\frac{1}{6} \sum\limits\_{v \in \bigcup F\_i} x\_v + \frac{3}{16} \sum\limits\_{v \in \bigcup C\_i} x\_v \geqslant 1$, implying $\sum\limits\_{v \in V} x\_v \geqslant \frac{16}{18} \sum\limits\_{v \in \bigcup F\_i} x\_v + \sum\limits\_{v \in \bigcup C\_i} x\_v = \frac{16}{3} \left(\frac{1}{6} \sum\limits\_{v \in \bigcup F\_i} x\_v + \frac{3}{16} \sum\limits\_{v \in \bigcup C\_i} x\_v \right) \geqslant \frac{16}{3}$. Moreover, the inequality is strict if some $x\_v$ with $v \in F\_i$ is not zero. Hence, in each optimal LP solution, non-zero weights are assigned only to vertices from $C\_i$'s. Moreover, it is possible to prove that there is only one optimal solution, with all weights of $C\_i$'s set $1/3$. It is not too important, though, because we already proved that all optimal LP solutions are pairwise disjoint from all optimal OCT's.

# Answer
> 0 votes
Wouldn't that imply one could solve odd cycle transversal simply by solving the LP finding a positive vertex removing it from the graph and repeating?

---
Tags: graphs, optimization, linear-programming
---


title: alpha equivalence of lambda calculus

text:
# Question
Title: alpha equivalence of lambda calculus
I am pretty new in λ calculus. And I am now trying to understand Alpha equivalence. Basically can I think it in this way: as long as I make sure all the bound variables and their corresponding abstractions are noted as the same letter, the new expression is alpha equivalent to the old one? Here is one example:

```
 (λx.(λx.x(λy.x)x)x)x

```

And by applying alpha equivalnce I can rewrite it to:

```
  (λw.(λz.w(λy.z)z)w)x

```

Is my understanding correct ?

# Answer
> 3 votes
> Here is one example:
>
> ```
>  (λx.(λx.x(λy.x)x)x)x
>
> ```
>
> And by applying alpha equivalnce I can rewrite it to:
>
> ```
>  (λw.(λz.w(λy.z)z)w)x
>
> ```
>
> Is my understanding correct ?

There is a small error in your rewriting: at `λz.w` you have changed the meaning of the expression, because now the bound variable refers to the outer lambda abstraction, instead of the inner lambda abstraction as before. Instead, it should be `λz.z`. Other than this, the rewriting is correct.

> Basically can I think it in this way: as long as I make sure all the bound variables and their corresponding abstractions are noted as the same letter, the new expression is alpha equivalent to the old one?

Yes, this understanding is correct.

# Answer
> 2 votes
One way to not mess up with variable names in $\lambda$-calculus is to use De Brujin indexes. With this, $\alpha$-equivallence becomes a really obvious syntactic equality, for instance:

\begin{align\*} \lambda x.x &\rightarrow \lambda.0 \\ \lambda z.z &\rightarrow \lambda.0 \\ \lambda x .\lambda y. x &\rightarrow \lambda.\lambda.1 \\ \end{align\*}

Intuitively, these indexes can be though as the number of $\lambda$s you have to skip to make a variable bound.

\begin{align\*} \Bigg(λx.\Big(λx.x(λy.x)x\Big)x\Bigg)x &\rightarrow (\color{blue}{λx}.(\color{red}{λx}.\color{red}{x} (\color{green}{λy}.\color{red}{x})\color{red}{x})\color{blue}{x})\color{blue}{x} \\ (\color{blue}{λ}.(\color{red}{λ}.\color{red}{0} (\color{green}{λ}.\color{red}{1})\color{red}{0})\color{blue}{0})\color{blue}{0} &\rightarrow (λ.(λ.0(λ.1)0)0)0 \\ \end{align\*}

> And by applying alpha equivalnce I can rewrite it to:
>
> (λw.(λz.w(λy.z)z)w)x
>
> Is my understanding correct ?

Let's check:

\begin{align\*} \Bigg(λw.\Big(λz.w(λy.z)z\Big)w\Bigg)x &\rightarrow (\color{blue}{λw}.(\color{red}{λz}.\color{blue}{w}(\color{green}{λy}.\color{red}{z})\color{red}{z})\color{blue}{w})\color{blue}{x} \\ (\color{blue}{\lambda}.(\color{red}{\lambda}.\color{blue}{1}(\color{green}{\lambda}.\color{red}{1})\color{red}{0})\color{blue}{0})\color{blue} {0} &\rightarrow (\lambda.(\lambda.1(\lambda.1)0)0)0 \end{align\*}

Nope.

---
Tags: lambda-calculus
---


title: Converting PDA to CFG

text:
# Question
Title: Converting PDA to CFG
I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\ \Gamma$ for $\[pXq\]$ we have include the sequence of derivations which would pop *X* from the stack.

I partially understand what is going on but I cannot seem to understand how do I unroll the productions to form strings so I can understand it clearly. Take the production (5) in the example for instance. From what I understand it we are in state p we want to pop A and in the end we should be in state p with empty stack. As we are reading *0* we have zero in the production followed by $\[pAq\]\[qAp\]$, this is the thing which I am not understanding because if we look at the PDA there is no way of going to *q* on reading 0. I would like to know what really is going on.

A related question is answered here but I cannot understand it how to clear my confusion.

# Answer
You have the basic intuition right. The variable $\[p,A,q\]$ represents the set of (strings accepted by) computations from state $p$ to state $q$ that will pop the topmost symbol $A$ from the stack.

Technicaly the relation between grammar $G$ and pda $M$ is given on the top of the slide you show.

Then the construction follows recursion. If the pda pops $A$ but pushes $B\_1B\_2B3$ the grammar will replace the computation on $A$ starting in $p$ and ending in $q$ into three separate computations $\[q\_1,B\_1,q\_2\]\[q\_2,B\_1,q\_3\]\[q\_3,B\_1,q\]$. Here the intermediate states $q\_2,q\_3$ are unknown and are *guessed* by the grammar. Only $q\_1$ is known, as it is the state where the pda instruction moves to.

Your observation is right. This standard construction might introduce triplets $\[p,A,q\]$ that will be useless. In your example there will be no computations from $q$ to $p$ so a triplet $\[q,A,p\]$ is never used in a succesful derivation. That is not problamatic. The construction just produces all possibilities, and variables that turn out to be useless can be removed afterwards if one really wants.

**Note.** The other question you link to uses a different Sipser style automaton model! There stack symbols are pushed one by one without popping at the same time. To add to the confusion the answer given at that question perfectly matches the construction from your slide!
> 1 votes

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


# Question
Title: Is there a name for X when X bitwise OR Y is Y?
I'm wondering if there is a mathematical or computer science term for a number X such that `Y | X = Y`? For example:

```
66536 | 1000 == 66536

```

In this case, 1000 is the "insert name here" of 66536. Perhaps there is no name for this..? I've tried searching for "bitwise OR returns itself" and other such terms but without luck so far.

# Answer
> 3 votes
I would say that $X$ is a subset of $Y$, in terms of bits set.

---
Tags: terminology, bit-manipulation
---


title: Gaussian distribution with condition?

text:
# Question
Title: Gaussian distribution with condition?
# What does this expression mean?

## Normal distribution with condition

I am reading a research paper and found the following expression (Eq.28 in the paper below).

It means a Gaussian distribution, but the mean component seems conditional probability-like expression $\it{\bf{s}}\_t | \it{\bf{m}}\_{b, t, m}^{(j)}$. I have never seen this expression before and cannot find any info about it.

The variables $\it{\bf{s}}\_t$ and $\it{\bf{m}}\_{b, t, m}^{(j)}$ are both vectors and $\bf{\Sigma}\_{b}$ is a covariance matrix.

Does anybody have an idea of what this expression means?

## Original paper where the expression is.

The original paper can be found here: https://eprints.soton.ac.uk/437941/1/08340823.pdf

Thanks in advance.

# Answer
$$\mathcal{N}(x|m,\Sigma)=(2\pi)^{-k/2}|\Sigma|^{-1/2}\exp\left(-2^{-1}(x-m)^T\Sigma^{-1}(x-m)\right)$$

where $x,m$ are vectors of dimension $k$, $\Sigma$ is a $k\times k$ matrix, $|\Sigma|$ is its determinant. The vector $m$ represents the mean of the multivariate normal, and $\Sigma$ the covariance matrix, which must be positive definite.
> 1 votes

---
Tags: statistics, bayesian-statistics, robotics
---


# Question
Title: Do any two spanning trees of a simple graph always have some common edges?
I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to prove or disprove this conjecture?

# Answer
> 47 votes
No, consider the complete graph $K\_4$:

It has the following edge-disjoint spanning trees:

# Answer
> 14 votes
For the more interested readers, there are some research on decomposition of graph into **edge-disjoint spanning trees**.

For example, the classical papers On the Problem of Decomposing a Graph into $n$ Connected Factors by W. T. Tutte and Edge-disjoint spanning trees of finite graphs by C. St.J. A. Nash-Williams provides a characterization of graphs that contains $k$ pairwise edge-disjoint spanning trees.

For example, the paper Bi-cyclic decompositions of complete graphs into spanning trees by Dalibor Froncek shows how to decompose complete graphs $K\_{4k+2}$ into isomorphic ${2k+1}$ spanning trees.

For example, the paper Factorizations of Complete Graphs into Spanning Trees with All Possible Maximum Degrees by Petr Kovář and Michael Kubesa shows how to factorize $K\_{2n}$ to spanning trees with a given maximum degree.

You can search for more. For example, a Google search for decomposition of graph into spanning trees.

# Answer
> 9 votes
**EDIT: This is incorrect as pointed out in the comments. As the other answer says, a spanning tree for $K\_4$ can be done without sharing edges.**

No, it's not true that any two spanning trees of a graph have common edges.

Consider the wheel graph:

You can make a spanning tree with edges "inside" the loop and another one from the outer loop.

# Answer
> 3 votes
After observing the graphs presented by @Bjorn and @Gokul, I arrive at the conclusion that every complete graph $K\_n$ with $n\geq4$ has at least two spanning trees with disjoint edges.

The graph given in the pic, which is wheel, has clearly two spanning trees with disjoint edges. In fact, every wheel will have **exactly** $2$ spanning trees with disjointed edges because one is complement graph of another.

Now, If we look at the solution of @Bjorn carefully, we find that his graph & spanning trees are homomorphic to the graphs shown in the pic. In fact, every complete graph $K\_n$ with $n\geq4$ has wheel as its subgraph, so it directly follows that every complete complete graph with $n\geq4$ has **at least 2** (or exactly $2$?) spanning trees with disjoint edges.

**P.S**: This observation gives birth to $2$ more interesting question.

1. Is there any complete graph with more than $2$ spanning trees with disjoint edges? Or it will always have exactly $2$ spanning trees with disjoint edges.
2. Is there any graph other than wheel or wheel as its subgraph having spanning trees with disjointed edges?

# Answer
> 1 votes
For $K\_{2k}$, I believe that

$$G\_1 = \\{ (v\_{2i},v\_{2i+1} ),(v\_{2i},v\_{2i+2}),\dots,(v\_{2k-2},v\_{2k-1})\\},$$

$$G\_2 = \\{ (v\_{2i+1},v\_{2i+2}),(v\_{2i},v\_{2i}),\dots(v\_{2(k-1)},v\_{2(k-1)})\\}$$

for $0\leq i \< k$ are counterexamples. That is, for the first graph, take the vertices with even indices and connect them to the next vertex, and for all but the last even vertex, connect it to the vertex after that as well. For the second graph, do this with odd vertices.

And inductively, once we have a counterexample for $n$ vertices, it's easy to construct a counterexample with $n+1$ vertices by connecting the new vertex with one edge for one graph, and with another edge for the other.

# Answer
> 1 votes
We can show that any complete graph of size $n \> 3$ has two edge-disjoint linear trees. Choose $1 \< k \< n-1$ relatively prime to $n$; this is always possible when $n \> 3$. One spanning tree is obtained by the edges $$ E\_1 = \\{ \\{i, i+1\\}: 0 \leq i \< n-1\\} $$ where we identify the vertices with $\\{0, \ldots, n-1\\}$. For the second tree define $j\_0 = 0$ and $$ j\_{i+1} \equiv j\_i + k\ \mathrm{mod}\ n $$ and set $$ E\_2 = \\{\\{j\_i, j\_{i+1}\\}: 0 \leq i \< n-1\\}. $$ This defines a spanning tree because $k$ is an additive generator of $\mathbf{Z}/n\mathbf{Z}$.

Suppose $e \in E\_1 \cap E\_2$ and $e = \\{i, i+1\\}$. This means that either $$ i+1 \equiv i+k\ \mathrm{mod}\ n \implies k \equiv 1\ \mathrm{mod}\ n $$ or that $$ i \equiv i+1+k\ \mathrm{mod}\ n \implies k \equiv -1\ \mathrm{mod}\ n. $$ The first is impossible because $k \> 1$, and the second is impossible because $k \< n-1$.

# Answer
> 0 votes
If the graph has a bridge (i.e. an edge whose removal disconnects the graph), then this edge must belong to every spanning tree. Intuitively, a bridge is the only edge connecting its two endpoints and so necessarily belongs to every connected subgraph.

On the other hand, if an edge of the graph belongs to a cycle, then there exists a spanning tree not containing this edge.

So, if every edge of a graph belongs to a cycle, then no edge is common to all spanning trees (i.e., the intersection of the edge sets of the spanning trees is the empty set).

---
Tags: graphs, spanning-trees
---


# Question
Title: How to prove that the dual linear program of the max-flow linear program indeed is a min-cut linear program?
So the wikipedia page gives the following linear programs for max-flow, and the dual program :

While it is quite straight forward to see that the max-flow linear program indeed computes a maximum flow (every feasable solution is a flow, and every flow is a feasable solution), i couldn't find convincing proof that the dual of the max-flow linear program indeed is the LP of the min-cut problem.

An 'intuitive' proof is given on wikipedia, namely : $d\_{uv}$ is 1 if the edge $(u,v)$ is counted in the cut and else $0$, $z\_u$ is $1$ if $u$ is in the same side than $s$ in the cut, and $0$ if $u$ is in the same side of the cut than $t$

But that doesn't convince me a lot, mainly why should all the variables be integers, while we don't have integer conditions ?

And in general, do you have a convincing proof that the dual of the max-flow LP indeed is the LP formulation for min-cut ?

**Edit** : Ok i found a proof here http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf , however it only gives a probabilistic way to build the cut from the variables assignement of the LP.

# Answer
We can write the constraints on the $d\_{uv}$ as follows: $$ d\_{uv} \geq z\_u - z\_v, z\_v - z\_u $$ $$ d\_{sv} \geq 1 - z\_v $$ $$ d\_{ut} \geq z\_u $$ Since we are minimizing $\sum d\_{uv} c\_{uv}$ and $c\_{uv} \> 0$, this means that we want to minimize each individual $d\_{uv}$, and so in fact $$ d\_{uv} = |z\_u - z\_v| $$ $$ d\_{sv} = 1 - z\_v $$ $$ d\_{ut} = z\_u $$ If we put $z\_s = 1$ and $z\_t = 0$, then the formula $$ d\_{uv} = |z\_u - z\_v| $$ holds for all $u,v$.

We can think of $z\_v$ as specifying the position of the vertices on the real line. We are penalized $c\_{uv} |z\_u - z\_v|$ for each edge $(u,v)$. Furthermore, $z\_s = 1$ and $z\_t = 0$. From this description, it is evident that there is no reason to put any vertex beyond the interval $\[0,1\]$.

If $z\_v \in \\{0,1\\}$ for all $v$, then we can think of the $z\_v$ as specifying a cut: one side (which includes $s$) consists of all $v$ such that $z\_v = 1$, and the other side (which includes $t$) consists of all $v$ such that $z\_v = 0$. If we allow general $z\_v \in \[0,1\]$, then we can think of it as a "fractional cut".

It is natural to ask whether fractional cuts are better than cuts. It turns out that they aren't. The simplest way to see this (same proof as in Luca Trevisan's lecture notes) is to construct the cut *randomly*: choose a threshold uniformly at random in $\[0,1\]$, and use it to partition the vertices into those left of the threshold and those right of the threshold. The probability that two vertices $u,v$ are in different sides of the cut is exactly $|z\_u - z\_v|$, and so the expected weight of the cut is $\sum\_{uv} c\_{uv} |z\_u - z\_v|$.

This is a very simple example of the *metric method* in the design of algorithms.
> 1 votes

---
Tags: linear-programming
---


title: Contour pushing algorithm

text:
# Question
Title: Contour pushing algorithm
I'm implementing push contour feature for web application. It is an ability to change the contour by touching it. Mouse pointer becomes a circle that bumps contour (like in Photoshop). Contour is *polyline* object and pushing circle is some point with defined radius.

Sequence of actions on `mousemove` is following:

1. Detect points in polyline that are closer to pushing point than defined radius
2. push those points or just draw circle segment in the defined area.

**Questions:**

1. How to determine points that are need to be pushed? I can iterate all segments in polyline (300-600 segments) and calculate distance for each like here: https://gist.github.com/mattdesl/47412d930dcd8cd765c871a65532ffac . But in this case full iteration 60 times per second is quite performance hard. May by some algorithm can do it more afficient?
2. How to push the point? we can't just change it position. As 1 point finally can become 2 points. It is more like drawing circle segment.

# Answer
> 0 votes
After some time of investigation and development I came up with some type of hybrid "Greiner–Hormann clipping algorithm" implementation and other approaches.

Following steps were used:

1. At first - generate two circles-polygons based on previous and current mouse move position.
2. Merge them using Convex Hull calculation by implementation Graham scan algorithm.
3. Detect all intersections between polyLine and generated capsule. Details:

4. Traverse two polygons and generate new one based on union/subtraction mode. Notes:

* traversal direction is chosen by sorted polar angle - to cover shared segments that Greiner–Hormann can not handle;
* starting point is calculated as one of the extreme vertices;
* for subtraction mode we traverse all possible polygons. Than we pick up one with the biggest area;
* detecting polygon order implements Shoelace algorithm (https://en.wikipedia.org/wiki/Shoelace\_formula).

5. Optimize contour by removing:

* duplicates;
* close points, that are located closer than 1 pixel;
* points in one line by keeping only edges of the line.

# Answer
> 1 votes
I suggest you use a data structure for nearest neighbor search to speed up the process of finding all points in the polyline that are closer than the defined radius. That should lead to a significant speedup.

---
Tags: algorithms
---