# Question
Title: Modifying the probability of sucess of an algorithm
This is motivated from a homework question. Let $A$ be an algorithm with probability of success equal to $q$ for solving a given problem. Let $p \in (0, 1)$. Find an algorithm that has a probability of success of at least $p$.

My idea so far is to run the algorithm multiple times and counting the number of times the algorithm succeeds and fails, but I don't know how I should combine the results to give an answer.

# Answer
> 2 votes
In general you can't. Suppose the problem is a yes-or-no question, so that guessing randomly has a 50% chance of being right, but the problem is extremely hard or is unsolvable. Thus there is a trivial algorithm $A$ (that guesses randomly) with $q=0.5$, but there might not be any way to solve it with success probability $p\<0.5$. For instance, maybe the problem is "guess what bit I am thinking of"; then there is no such solution.

However if you have a way to verify whether a solution is correct, then as Yuval Filmus explains, you can do it. You can simply run $A$ a few times, checking each time to see whether it gave the correct answer and outputting the first correct answer. This will increase the probability of getting a correct answer. You can figure out how many times you need to re-run $A$ using simple mathematics (hint: each run is independent).

---
Tags: algorithms, randomized-algorithms, randomness
---


# Question
Title: Storing a file by converting it into $n$ files, some of which can be lost
Let's say that I have a file that I really don't want to lose.

I want to convert the *original file* into $n$ files in the way that will allow me to recover the original file if I have **any** $m$ of the *converted files*. I want an algorithm that will solve this problem for any given $m$ and $n$, where $0 \< m \< n$.

A trivial way to do it would be to just have $n$ copies of the original file but I want the *converted files* to be **as small as possible**.

Is there a name for the problem that I am trying to describe? I tried googling things like "redundant encoding" but I was not able to find what I am looking for. Error-correction algorithms seem to deal with some bits of the file lost or corrupted but in my case each of the *converted files* is either lost completely or fully available and uncorrupt.

I would really appreciate if someone would tell me where to look for existing approaches to solving this problem. Thanks in advance!

# Answer
This is called erasure coding. Here each file represents a single symbol, and erasure codes allow to handle erasure of any $n-m$ symbols, i.e., loss of any $n-m$ files. There are many standard schemes that have been proposed.
> 2 votes

# Answer
Let $p \geq n$ be prime, and suppose that $p \leq 2^k$; we would like $p$ to be as close to $2^k$ as possible. Convert your input into chunks of $mk$ bits, and interpret each chunk as $m$ integers $0 \leq a\_0,\ldots,a\_{m-1} \< p$. Define a polynomial $$ P(x) = a\_0 + a\_1 x + \cdots + a\_{m-1} x^{m-1}. $$ For $0 \leq i \leq n-1$, the $i$'th copy will encode this chunk as $P(i) \bmod p$.

The idea is that given the values of $P(i)$ for $m$ many values of $i$, we can use Lagrange interpolation to recover $a\_0,\ldots,a\_{m-1}$. This amount to solving a certain system of linear equations.

For the experts: we can use any finite field of size at least $n$. If we choose a finite field of characteristic 2, then computations become more difficult, but the encoding scheme becomes completely lossless.
> 2 votes

---
Tags: algorithms, data-compression
---


# Question
Title: Largest rectangle covering set bits in a bitmap
I have a 2D bitmap with various shapes (each pixel is either 1 or 0).

How can I find the largest axis-aligned rectangle that covers only set pixels?

# Answer
> 1 votes
It can be done in $O(n^3)$ time, for a $n\times n$ bitmap.

Let $A$ denote the image, so $A\[i,j\]$ is the pixel at coordinates $(i,j)$.

For each pixel $(i,j)$, let $H\[i,j\]$ denote the height of the column of all-1 pixels below it, i.e., the largest $h$ such that $A\[i',j\]=1$ for all $i' \in \[i,i+h-1\]$.

For each pixel $(i,j)$ and each height $h$, let $W\[i,j,h\]$ denote the width of the rectangle of height $h$ with upper-left corner at $(i,j)$ that has covers only set pixels, i.e., the largest $w$ such that $H\[i,j'\] \ge h$ for all $j' \in \[j,j+w-1\]$.

You can compute each element of $H$ in $O(1)$ time using dynamic programming (fill them in from the bottom up). Also, once you have $H$, you can compute each element of $W$ in $O(1)$ time using dynamic programming (fill them in the right to left).

Finally, once you have $W$, it is trivial to find the largest rectangle, by scanning all of its elements.

In other words, if you have a $n\times n$ bitmap, you can fill in $H$ in $O(n^2)$ time and fill in $W$ in $O(n^3)$ time, and then you can find the largest rectangle in $O(n^3)$ time. So, this gives an $O(n^3)$ time algorithm. That is an improvement over Pål GD's algorithm, which takes $O(n^4)$ time.

If the bitmap is rectangular rather than square, you can use the same algorithm. I suggest you transpose it first if it is taller than it is wide; that way you will have fewer values of $h$ to iterate over. In this way, if you have a $m\times n$ bitmap, the running time will be $O(\min(mn^2,m^2n))$.

---
Tags: algorithms
---


# Question
Title: Deciding whether a set of relations can be composed to the empty relation
Is there an efficient algorithm to solve the following decision problem?

> Given a finite set $S$ and a set of relations $\mathcal R$ from $S$ to $S$, determine whether there is any sequence of relations $r\_1,r\_2,\ldots,r\_k\in\mathcal R$ such that $$r\_1\circ r\_2\circ \ldots\circ r\_k = \emptyset$$ where $\circ$ is the usual composition of relations and $\emptyset$ is the empty relation.

---

This question came up as a simplification of some problems that arose while trying to implement and somewhat generalized version of the foetus termination checking algorithm in an efficient way. The question is mostly of theoretical interest to me - for the most part, I would expect inputs to such an algorithm to be small, especially after applying various algorithms that can handle common special cases of this problem. The question is interesting to me since it doesn't seem to be related to any other decisions problems I'm aware of, even after several days of thinking.

There are several ways to solve this in general, but all that I know of require at least exponential time in $|S|$.

The most obvious way (and, essentially, what the paper suggests) would be to take the closure of $\mathcal R$ under $\circ$ and just check whether $\emptyset$ is in this closure - although such a closure may contain many elements, so this is potentially very expensive (e.g. it only takes two elements of $\mathcal R$ to generate the the $|S|!$ elements of the symmetric group).

A somewhat more efficient way would be to consider the set $P(S)$ of subsets of $S$ and to consider a directed graph upon it where there is an arrow from $A$ to $B$ whenever $B=r\[A\]$ for some $r\in\mathcal R$ (where $r\[A\]$ is the image of $A$ under the relation $r$ \- that is, all $y$ such that $(x,y)\in r$ for some $x\in A$). We could then search for a path from $S$ to $\emptyset$ in this graph. This is an improvement over the naive algorithm, since a straightforwards implementation of this would only have time complexity $O(|R|\cdot 2^{|S|})$ (at worst - I haven't proven any lower bound on the time complexity, just this upper bound).

Is this decision problem one that's been studied? Does it have a good algorithm or a reduction to a known hard problem?

# Answer
Your problem is equivalent to NFA (non)universality.

Consider an NFA on alphabet $\Sigma$, states $Q$, initial state $q\_i$, final states $F$, and a transition relation.

We construct an instance of your problem as follows:

* The set $S$ is $Q$.
* For each $\sigma \in \Sigma$, there is a relation $R\_\sigma$ consisting of pairs $(q,r)$ such that the NFA contains a transition from $q$ to $r$ labelled $\sigma$.
* There is a relation $R\_f$ consisting of pairs $(q,q\_i)$ for all $q \in F$.

Suppose that the NFA doesn't accept some word $w = \sigma\_1 \ldots \sigma\_n$. I claim that $$ R\_f \circ R\_{\sigma\_1} \circ \cdots \circ R\_{\sigma\_n} \circ R\_f = \emptyset. $$ Indeed, suppose that $(q,q\_f)$ belongs to the relation on the left. Thus there exist $q\_0,\ldots,q\_n$ such that:

* $q R\_f q\_0$: thus $q\_0 = q\_i$.
* $q\_0 R\_{\sigma\_1} q\_1, \ldots, q\_{n-1} R\_{\sigma\_n} q\_n$: thus the NFA could be at state $q\_n$ after reading $w$, implying that $q\_n \notin F$.
* $q\_n R\_f q\_f$: impossible, since $q\_n \notin F$.

Conversely, suppose that the NFA accepts all words; in particular, $q\_i \in F$, since the NFA accepts the empty word. This assumption directly implies that if $R$ is a composition of relations $R\_\sigma$ (where $\sigma \in \Sigma$) then there exists $q\_f \in F$ such that $q\_i R q\_f$. We think of such compositions as new relations $R\_w$, where $w \in \Sigma^\*$.

Consider now an arbitrary composition of relations $R\_w,R\_f$, we the added restriction that no two $R\_w$'s appear next to each other. We claim that for any such composition $R$:

* If $R$ ends with $R\_w$, then there exists $q\_f \in F$ such that $q\_i R q\_f$.
* If $R$ is empty or ends with $R\_f$, $q\_i R q\_i$.

This is clear for the empty composition (which fits both cases). Now we consider two cases:

* If $R = S \circ R\_w$, then according to the inductive hypothesis, $q\_i S q\_i$, and so $q\_i R q\_f$ for some $q\_f \in F$ as mentioned above.
* If $R = S \circ R\_f$, then $q\_i S q\_f$ for some $q\_f \in F$ (since $q\_i \in F$), and so $q\_i R q\_i$.

This shows that no composition is empty.

Summarizing, there is an empty composition of relations iff the NFA is not universal. Since NFA universality is PSPACE-hard, so is your problem (recall PSPACE=coPSPACE). On the other hand, your problem is the special case of NFA non-universality in which all states are initial and accepting: the relations correspond to the alphabet of the NFA, just as in the construction above. Since NFA universality is in PSPACE (even when several initial states are allowed!), so is your problem. The problem is thus PSPACE-complete.
> 3 votes

---
Tags: decision-problem, sets, finite-sets
---


# Question
Title: What is the correct way to draw NFA of RE (a|b|c)?
We were assigned to draw NFA for regular expression `a|b|c`, so like any one I draw this

But my professor told me it is wrong, the correct way is

So, I checked it on online tools toolbox by cyberzhg, and regexper and according to both of them I am also correct.

Professor's argument was in maths for `4+5+1`, we first add either `4+5` or `5+1` together then we add result of it with the remaining number. That is why for `a|b|c`, the correct solution is either `(a|b)|c` or `a|(b|c)`.

Can you please tell are we both correct?

# Answer
> 22 votes
There is no unique way of converting a regex into NFA. That is, for any regular language $L$ there exist multiple (even, infinite) number of NFAs that accept the language $L$.

The solution of your professor restricts each state to have at most 2 outgoing states, while your solution does not. Unless this restriction was required by the professor somehow, both solutions are equivalent in the sense they both accept the language $L=\\{a, b, c\\}$ defined by the regexp `a|b|c`.

Note, that the professor might wanted you to work in methodological way, where there are fixed "gadgets", i.e., converting `x|y` to some certain states, and converting `xy` to other (fixed) states. Then, their comment makes sense - they wanted you to interpret `a|b|c` as `(a|b)|c`, first use the gadget on `a|b` to obtain the upper half of the machine, and then use the gadget again on `x|c` where $x$ is the already-constructed machine. If this (or any fixed other) methodology was required, then the outcome NFA would be unique.

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


# Question
Title: How is the time complexity of a non-deterministic Turing machine defined?
I read different things online about this:

In Sipser, p. 283. The time-complexity of a NTM is defined as the maximum number of steps it uses on any branch on any input of length n. So this is only defined for a decider.

In other sources (like the lecture notes I inherited from my predecessor at the university I work at, and a number of pages online like e.g. here: http://www.mi.fu-berlin.de/wiki/pub/ABI/ComputabilityComplexity/Complexity.pdf), it is defined as the maximum over the minimum number of steps in a path leading to acceptance for strings of length n in the language, and 0 (or sometimes 1) if the language does not contain any strings of length n.

So in the latter, the runtime is considered to be the length of the shortest accepting path, if it exists and 0 (or 1) if it doesn't. This last part is giving me a headache.

But there is something strange in Sipser's definition too. The runtime on a string that is accepted may be exponential if at least 1 path in the tree that does not accept the string is exponential, even if 1 (or all) paths that accept the string are polynomial.

Which of both is now correct? (Part of my confusion originates from whether or not a problem in NP requires a NTM that halts on any input.)

\[EDIT\] (added an example of the second definition) Based on the 2nd comment below, I found a similar comment on their equivalence in Hopcroft, Motwani and Ullman on page 432.

But using this equivalence, is it then not possible to construct a halting TM for any non-halting one?

# Answer
> 1 votes
It's always possible to limit running time of any TM or NTM to a bound by counting number of steps of execution and rejecting if too much time was used, if your time bound is large enough that such counting is available. Note though that this requires counting the size of input and computing the number of steps after which the bound is exceeded, and then counting the number of computation steps actually used and rejecting if bound is exceeded. This could be difficult if you don't know constant factor associated to the bound, or if the asymptotic bound itself is not known. The constant factor can usually be estimated, it's only important that it's sufficiently large for the used machine. Typically you would avoid the problem with constant factors by measuring time by (only) counting how many times loops or recursively invoked branches in the algorithms are executed.

There is a risk of changing the problem and producing wrong answers if you do not know that all accepting paths accept before the time bound, and if you limit the running time anyway. This of course must be avoided.

I used to speculate whether it would be possible to solve the P=NP problem by declaring that P != NP, because time is measured differently in P compared to in NP, since concurrent computation can explore many alternatives in one time step where sequential computation must check and search them sequentially. But of course the question is not quite that simple, as you would also need to prove that simulators can't compensate for the difference.

---
Tags: turing-machines, time-complexity, np, nondeterminism
---


# Question
Title: Request for Good Encyclopedic works of computer science
I attempt to find a few general encyclopedic works on computer science such that looking up relevant terminologies is easily available ready to hand. I'm not familiar with the whole picture of computer science so I can't describe precisely the delicate character of what is a good encyclopedic reference to computer science. But I could list some extremely distinctive and appropriate(at least for my part) encyclopedic works on mathematics so as to provide a comparable template as suggetions for indicating that what type of general encyclopedic works on computer science are what I really desire. Any suggetions are really appreciated.

Some famous and useful Encyclopedias of Mathematics:

### 1. Encyclopedia of Mathematics

Encyclopedia of Mathematics(`EOM` for short), published by `Kluwer Academic Publishers in 2002`, maintained by `Michiel Hazewinkel`. The encyclopedia has been translated from the Soviet `Математическая энциклопедия` (Matematicheskaya entsiklopediya) (1977, Moscou, Sov. Entsiklopediya) originally edited by `Ivan Matveevich Vinogradov`. References listed in many articles seem heavily weighted in favour of Russian mathematicians, reflecting the works Russian origins. You can really consider EOM as professional, comprehensive and up-to-date reference or manual of Mathematics because at present EOM possesses its own online wiki. It's open access and you can look up through the following link: EOM, which is maintained by `Springer`, in cooperation with the `European Mathematical Society`. EOM is currently the most comprehensive, professional and up-to-date **ONLINE** mathematics reference work.

### 2. Encyclopaedia of Mathematical Sciences

Encyclopaedia of Mathematical Sciences(`EOMS` for short), published by `Springer-Verlag`. The series started as a joint effort with the `Soviet publisher VINITI`, and it then became the famous and high-quality mathematical Encyclopaedia, which presented a series of surveys in contemporary mathematics written by/with the cooperation of the foremost specialists worldwide. For example, one could have a look at this very good survey volume `Basic Notions of Algebra`(really appropriate for everyone to get a bird's eye view of the totality of modern algebra) written by a master `Igor R. Shafarevich`. The articles contained in volumes of EOMS report on a variety of topics in terms of the major concepts and results, without giving details of proofs. So if you find the explanations of some topic in EOM are not so deep and detailed you could try to consult EOMS alternatively.

### 3. 岩波数学辞典

岩波数学辞典(Iwanami Sūgaku Ziten, `ISZ` for short), published by `岩波書店(Iwanami Shoten)`. The `2nd and 3rd` Japanese original edition had been translated into English volumes with title `Encyclopedic Dictionary of Mathematics`(`EDM` for short; Note: `EDM_1=ISZ_2, EDM_2=ISZ_3`). The latest Japanese revised version is the 4th edition(i.e., `ISZ_4`) and it has no other language translations so far.

First of all, it's well worthy of going through the following paragraphs extracted from the prefaces of `ISZ_1` and `ISZ_2` written by `S.Iyanaga`:

> \`\`One of the characteristics of 20th-century mathematics is the conscious utilization of the axiomatic method and of general concepts such as sets and mappings, which serve as foundations of different theories. Indeed, `mathematics is being reorganized on the basis of topology and algebra`. One such example of reorganization is found in `Bourbaki's Eléments de mathématique`; ...This encyclopedia, with its limited size, cannot contain proofs for theorems. However, we intend to present a lucid view of the totality of mathematics, including its historical background and future possibilities. Each article of this encyclopedia is of `medium length` sufficiently short to permit the reader to find exact definitions of notions, and sufficiently long to contain explanations clarifying how important concepts in the same field are related to each other.''

> \`\`It's an encyclopedic dictionary with articles of `medium length` aimed at presenting the whole of mathematics in a lucid system, giving exact definitions of important terms in both pure and applied mathematics, and describing the present state of research in each field, together with historical background and some perspectives for the future.''

The above citations might be distilled into two crucial points:

* `Embracing Bourbaki's point of view on mathematics.` The domain of mathematics has been becoming a tower of Babel, in which autonomous disciplines have been becoming more and more widely separated from one another, not only in their aims, but also in their methods and even in their language. `Bourbaki`, which is in fact the collective pseudonym of a group of younger French mathematicians with a deeply integrative sense of mathematics who set out to publish an encyclopedic work covering most of modern mathematics, undertook the task of presenting the whole picture of mathematical knowledge in a systematic and unified fashion. The right paradigm or pattern of doing mathematics in the light of `Bourbaki's philosophy` is to recognize, specify and study the diverse structures. Bourbaki regards mathematical research as a research of structures in relation to three `mother-structures` which are precisely algebra, topology and order. Actually `algebraic and topological structures` are indeed two of the most important mathematical structures, and algebra and topology were probably the branches on which Bourbaki exerted his most profound influence. However, good structuralist approach does not search for the `formal structuralism`(just as done in `Théorie des ensembles`), but for the `right structuralism`(just as done in `Groupes et algèbres de Lie`). `ISZ` assimilated, to the greatest extent possible, the best of Bourbaki's structuralist ideas, i.e., the `algebra & topology-based` structuralist approach.
* `Adopting the organization method of ``Article with Medium Length''.` Here the `Article` is exactly the incarnation of the `Entry` in Encyclopedia. Keep this equation `Article = Entry` in mind. The text of `ISZ_4`, on the one hand, puts the whole of mathematics into 23 divisions(regarded as 23 branches of mathematics), for example, `IV theory of numbers, VI algebraic geometry`, on the other hand, consists of `515`(i.e., the numerical order in `Systematic List of Articles`(`SLA` for short)) articles arranged alphabetically. Most of these articles are divided into sections, indicated by `A, B, C, ..., AA, BB, ...`. Citations in the indexes are also given in terms of article and section numbers. We might consider the classification scheme mentioned above as an `ISZ Tag System`. Every article or section of article is tagged with a unique symbol sequence. Take an example for brief demonstration: the section `generalized Jacobi variety` is numbered `261 (VI-2) H`, which means that the path of the item on generalized Jacobi variety in the `ISZ Tag System` is designated by `SLA-261/division-VI/article-2nd/section-H`. Adopting the `Article with Medium Length` in the sense of `ISZ` endows the dimension of article or section of article with flexibility in organizing them with scalable length.

Compared to the `ISZ_3`, the `ISZ_4` edition adds more than 140 new entries, and many of the older entries have been either completely deleted or substantially revised. The number of entries has increased from `450` in the `ISZ_3` to `515` in the `ISZ_4`. The new added entries are mainly related to the modern and mainstream concepts, the prominent and extraordinary achievements obtained in the second half of the twentieth century. `ISZ_4` is as complete and comprehensive a magnum opus as one could wish for. It's succinctly but thoroughly covers all areas of mathematics, from the basics to the most advanced, for instance, the latest results such as `Fermat's theorem` and `Poincaré conjecture`, as well as an ever-expanding range of applications in recent years.

Within its `2000-plus pages`(`2016 pages in the 4th Japanese edition, 2007`) are elegant explanations of `Riemann surfaces, Fourier series, Hodge theory, l-adic cohomology`, and so forth. What's more, many of entries start at elementary level, builds into intermediate level and culminates with advance level. Each entry is accompanied by a list of the most recent references. In addition to the `515` entries, a `detailed index` serves as a collection of technical terms. So it's very convenient to look up terminologies occurring in your specific textbook in hand, which seems somewhat like you making use of a word dictionary such as the `OED`. You could thus get a lot of pleasure out of reading those well written entries, many of which are treated in depth, and require solid mathematical background and great maturity on self-study. The `ISZ_4` as an excellent reference will definitely meet the expectations of those people who are specialist or common researchers working at the doctoral level, as well as readers who are involved in mathematics in some way.

# Answer
The art of computer programming by Don Knuth is more similar to the Bourbaki type work you mention (containing more than an encyclopedia). It is currently one of the best resources available on CS and akin to Euclid's elements for geometry. For a young field such as computer science (less than a century as a scientific area) it is arguably one of the most complete overviews of key aspects of the field (though by no means all encompassing).
> 3 votes

---
Tags: reference-request
---


# Question
Title: Bounding this probability in this Monte Carlo algorithm
Let $P$ be a YES-NO decision problem. Let $A$ be an algorithm for deciding on it such that it is correct with probability $4/5$, in both cases (YES an NO). Design an algorithm that is correct with probability at least $p$, in both cases (YES an NO).

This is my solution but I'm stuck at bounding the probability. Let be $B$ be an algorithm that runs $A$, $n$ number of times. Let $X\_i$ with $1\leq i \leq n$ such that $X\_i = 1$ if $A$ outputs $YES$ and, $X\_i = 0$ if $A$ outputs $NO$. Without loss of generality assume that $P=YES$ then $\Pr\[\text{B is correct}\] = \Pr\[\text{B = YES}\] = \Pr\[X \geq \frac{n}{2}\]$. I know that in this case $E\[X\] = \frac{4}{5}n$, but don't know what else to do.

# Answer
Assuming I understand this correctly...the true state is either YES or NO. You have an algorithm A that can detect the truth with probability 4/5 and fails with probability 1/5. You devise an algorithm B that just runs A $n$ times and decides that the truth is YES if B has a sufficient number of YES outcomes out of those $n$ trials. I think that works. You want to find the first values of $n$ and $x$ (with $n/2\le x\le n$) that satisfy:

$$\sum\_{y=x}^n {n\choose y} (4/5)^y (1/5)^{n-y} \ge p,$$ and $$\sum\_{y=0}^{x-1} {n\choose y} (1/5)^y (4/5)^{n-y} \ge p.$$

In that way, your decision rule for B - return a YES if there are at least $x$ yes outcomes in the $n$ trials - will work with probability at least $p$. If $n$ is odd then you really only need the first inequality.
> 2 votes

---
Tags: algorithms, randomized-algorithms
---


title: How to design PDA for this language?

text:
# Question
Title: How to design PDA for this language?
I'm having a hard time trying to build the PDA for this language: $$L=\\{a^nb^m: n,m \geq 1 \land m=4n+2\\}$$

I don't know how many $a's$ should I push into the stack when reading $a$, and how many $a's$ should I pop out of the stack when reading $b$, and how to reach the final state. Can anyone help me with this? Thanks for your help!

# Answer
The language can be rewritten as $a^nb^{4n}bb$ which is to say that for every a's there are 4 b's and after that, we just add two b's. One strategy would be to push four stack symbols after you read 1 a. And then pop those stack symbols one by one on reading b's. After your stack is empty (i.e. resets to the starting symbol) then you just proceed to read two b's. One small caveat, do remember that your language *must* contain at least 1 a since $n \ge 1$
> 3 votes

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


# Question
Title: What is the practical difference between "differentiable programming" and existing autograd libaries?
People have recently started talking about "differentiable programming". I have listened to some people talk about this at a philosophical level, but I don't see the practical difference between this and just existing Autograd libraries like PyTorch.

I understand that (at least according to some interpretation of "differentiable programming"), what makes it different is that it is an integrated part of a programming language. For example, in Julia, backprop/autograd is apparently a fundamental element of the language.

However, it seems to me that there isn't such a big difference between calling backprop as a library call to PyTorch, vs having it more integrated in the language. The library call to PyTorch is already very simple. **So how is "differentiable programming" actually different in a meaningful way from just calling a library like PyTorch or TensorFlow?**

# Answer
> 1 votes
You are essentially right: "differentiable programming" and automatic differentiation libraries (e.g. PyTorch and TensorFlow) are morally the same thing. However, when people talk about *differentiable programming* they are more likely to be considering the problem from a theoretical lens, working e.g. in programming language theory or type theory. On the other hand, PyTorch and TensorFlow or more practical software engineering tools rather than interested in a formal or theoretical study of what automatic differentiation is.

Put another way: programming languages theorists are interested in differentiable programming because they are interested in understanding the fundamental principles behind how PyTorch and TensorFlow work.

For example, here's a prototypical paper on differential programming from ICFP 2018:

In the paper, Elliot proposes a foundational theory of differentiable programs, how they can be written and composed, and how differentiation and techniques like back-propagation can be derived as part of this theory. That may or may not be relevant to engineers working on PyTorch and TensorFlow, who just want to "get the job done" and write a usable tool that works well in practice.

---
Tags: machine-learning, programming-languages
---


# Question
Title: Transforming from neighbour representation to grid representation
Assuming I have a list L of lists. Each list in L has four entries \[North, Ost, South, West\] which represents the neighbours of a point i on a grid. If the entry is 0, the grid neighbour is not occupied by another point.

For example L\[0\] = \[0,3,8,0\].

This means that point 1 (which is represented by the first list in L), has point 3 on the right side and point 8 below. On the left and the top, there is no point, these grid places are not occupied.

I am struggling with transforming from this list L representation to a coordinate representation for each point.

The points can be separated, they can form clusters but they don't have to.

With neighbour, I am only referring to one unit above/below/right/left. Any neighbours further apart are not considered.

I think this problem should be known, but I don't know what I should search for.

This task is part of an optimization problem I am trying to solve with a genetic algorithm. I am looking for the optimal arrangement of points on a grid. Since the solution is translational invariant I am trying to find an intrinsic representation of the points on the grid. The representation above is such a trial. Now I have the problem that I cant map from this intrinsic representation back to the grid representation.

# Answer
Pick an arbitrary node. Assign it the coordinates $(0,0)$. Now run any graph traversal algorithm -- say, depth-first search. When you visit a node, you know its coordinates. Now you can look at its neighbors and assign coordinates to each of its neighbors (if they already have coordinates, check that the old ones and the new ones are consistent; if not, then it's impossible to lay out the graph in the plane), and visit the neighbors (if not already visited). This will let you reconstruct all of the coordinates with running time linear in the size of the graph.

For nodes with no neighbors, you have almost no information about their location. You can keep track of these nodes and at the end put them anywhere off to the side (as long as they are not next to any other existing node or next to each other; but they can be as far away as you want).
> 1 votes

---
Tags: depth-first-search
---


title: Algorithmic problem on sliding windows

text:
# Question
Title: Algorithmic problem on sliding windows
Given a zero-indexed, unsorted array, $a$ of integers (can be positive, negative, or zero) of size $n$. A window of size $k~(k \< n)$ is defined as a subarray $a\[i...i+k\]$ for every $0 \leq i \leq n - k - 1$. The problem is to find the minimum difference between two elements present in the same window, for every window.

I was able to come up with the following algorithms:

1. Maintain an array of size $k$ for every window (can be reused for every window). Sort each of these and find the minimum difference between consecutive elements. This will take $\mathcal{O}(k)$ space (not accounting the space required for the output) and $\mathcal{O}(n\*k \log k)$ time.
2. A slightly clever optimization is to add the incoming element into the already sorted window (alike insertion sort) and remove the leaving element. This reduces the time to $\mathcal{O}(n\*k)$ while the space is same as above.

However, I am looking for an algorithm which runs in $\mathcal{O}(n\*\log k)$ time and possibly $\mathcal{O}(k)$ space.

Note: This is not a homework question but was asked to me in a software engineering interview.

# Answer
> 3 votes
If you use a balanced binary search tree (instead of just a sorted list), you can remove and add new items in $O(\log(k))$.

In addition, you want to keep a min-heap of the differences of consecutive elements in the tree.

When adding a new item to the window, say it was $b$, and its value is between two elements $a$ and $c$ (i.e, $a\<b\<c$) - you will want to remove the difference $c-a$ from the heap, and add the two new differences $c-b$ and $b-a$.

When removing an item from the window, $b$, and its immediate neighbors in the tree are $a$ and $c$ (such that $a\<b\<c$), then you will want to do the opposite of the insersion: remove $c-b$ and $b-a$ from the heap, and add $c-a$ instead.

All of those insersion \ deletion operations work in $O(\log(k))$, and querying the minimal difference from the heap takes $O(1)$ time.

---
Tags: algorithms, arrays
---


# Question
Title: Understanding how internal fragmentation occurs in systems using only paging with huge page size
The excerpt below is from the OS text by *Galvin et. al.*

> When we use a paging scheme, we have no external fragmentation: any free frame can be allocated to a process that needs it. However, we may have some internal fragmentation. Notice that frames are allocated as units. If the memory requirements of a process do not happen to coincide with page boundaries, **the last frame allocated may not be completely full**. For example, if page size is $2,048$ bytes, a process of $72,766$ bytes will need $35$ pages plus $1,086$ bytes. It will be allocated $36$ frames, resulting in internal fragmentation of $2,048 − 1,086 = 962$ bytes. In the worst case, a process would need n pages plus $1$ byte. It would be allocated $n + 1$ frames, resulting in internal fragmentation of almost an entire frame.

> The above screenshot is from "High-Performance Computer Architecture" by Georgia Tech... Here the instructor says, that the size of the process is till that much as shown by the grey brace in the right. And our system is such that we are allocating say 2 pages to the process, then the dashed portion is the internal fragmentation.

The problem which I am having is something as follows. I drew the situation as shown above. The virtual address space of the process is shown in green. On the left, I show the virtual address bits. Now, in computers, page sizes are usually in powers of 2. So the page offset I guess, however long, if the page size is less than the virtual address space size, then it shall equally divide the virtual address space of the process. ***Now if it is equally divided, the last portion of the virtual address space shall have the stack section, then how shall there be a \[internal\] fragmentation \[in the last part of the last page as shown in the above pictures\]?***

Suppose if we use a page size of $4 MB$ then :

The picture might be something like this I guess. Note that the portions shown in blue I guess are internal fragmentation. While the huge gap between heap and stack is not allocated frames in the main memory, so we need not bother about them... But I guess it depends on the size of the stack and the code, data, and heap portion. Whether they are aligned properly as per the page or not, to have internal fragmentation and I feel we can't just simply say that **only the last part of the last frame shall not be occupied and it is the only internal fragmentation**. Moreover, how is the *Galvin* text calculating the size of the process?

# Answer
> 2 votes
Internal fragmentation occurs because the OS cannot allocate less than one page to a certain process. This implies that the last chunk of code/data for a process will take one page no matter its size. The worst case scenario is when the code/data use several pages + 1 byte. You thus end up with a whole page lost to internal fragmentation.

Now you are right that the code/data doesn't necessarily fit into one page. This creates some internal fragmentation in the other pages. This internal fragmentation though is minimal considering that it can be as long as an instruction can be.

To determine the size of a process, the OS simply looks in the executable. Most compilers/linkers will split the code/data of a compiled program in pages already. This means that the loading of processes is quite simple (unless you have some dynamic linking which makes it more complex). The OS simply allocates the pages that the process needs according to what is laid out in the executable.

In dynamic memory allocation, the libc implementation keeps track of the data you have available and attempts to avoid internal fragmentation as much as possible.

# Answer
> 1 votes
Forget the stack, forget all the details of the memory layout. Internal fragmentation always happens, because the OS hands out memory in multiples of the page size, and consumers might not need the full page. Whatever portions of pages are unused are "internal fragmentation".

Under reasonable assumptions about allocation sizes, the bigger the page size, the bigger the average amount wasted by rounding up each allocation (or process, or arena, or however you slice it) to a whole number of pages. Therefore larger page sizes go hand-in-hand with larger losses to internal fragmentation.

Imagine throwing a pizza party where you tell the guests that if they want to attend, they have to order one or more entire pizzas for themselves, and not share with anyone else. How much pizza will get thrown out at the end of the day compared to a party where each guest takes one or more *slices*, instead?

---
Tags: operating-systems, memory-management, virtual-memory, paging
---


# Question
Title: How to compute total internal and external fragmentation
I want to find the total external and internal fragmentation. What I understand is that external fragmentation occurs when processes are loaded and removed from memory, causing memory to be broken into little pieces, and that internal fragmentation is the unused memory internal to a partition.

As an example, say I had the following memory holes: 50 KB, 400 KB, 130 KB, 300 KB, 150 KB, and 70 KB (in that order). Now I have the following processes that need the following memory space (in order): A = 230 KB, B =180 KB, C = 130 KB, D = 120 KB, E = 200 KB.

Using the **first fit** method, I have determined the following allocation:

50 KB hole is assigned 0 processes -\> 50 KB free
400 KB hole is assigned processes A and C -\> 40 KB free
130 KB hole is assigned process D -\> 10 KB free
300 KB hole is assigned process B -\> 120 KB free
150 KB hole is assigned 0 processes -\> 150 KB free
70 KB hole is assigned 0 processes -\> 70 KB free

So, based on my understanding of the definitions:

Total internal fragmentation = 50 KB + 150 KB + 70 KB = 270 KB
Total external fragmentation = 40 KB + 10 KB + 120 KB = 170 KB

Is this correct? Thanks.

# Answer
> 1 votes
First of all you need to specify whether your partitions are fixed size or variable size. In case they are using dynamic partitioning(variable size) the internal fragmentation will always be 0 since its defined only for fixed size partitioning. Now assuming your partitioning is static, total internal fragmentation will be the sum of all internal fragmentations. And for external fragmentation it is equal to the total free memory available(holes plus contiguous free memory). Therefore External fragmentation here will be (50 + 40 + 10 + 120 + 150 + 70)KB = the total free memory available = total unused memory. While internal fragmentation will be (40+10+120)KB the partitions which are not used will not be counted since they are not allocated to any process. External fragmentation is a superset of internal fragmentation in case of fixed size partitioning.

# Answer
> 1 votes
The first fit placement algorithm is used for dynamic allocation. In dynamic allocation, there is no internal fragmentation!!!! Internal fragmentation is a memory that was reserved by the process but was not used in dynamic allocation reserve memory by request of the process. If the process request is 50MB, then 50MB will be allocated so that all memory will be used. Only external fragmentation has to be counted. Just add all free partitions.

50 KB hole is assigned 0 processes -\> **50 KB free** 400 KB hole is assigned processes A and C -\> **40 KB free** 130 KB hole is assigned process D -\> **10 KB free** 300 KB hole is assigned process B -\> **120 KB free** 150 KB hole is assigned 0 processes -\> **150 KB free** 70 KB hole is assigned 0 processes -\> **70 KB free**

I am teaching OS, by the way. I hope that will help!

# Answer
> 0 votes
According to the problem ,process A is allocated to 400 KB memory ,so the memory is split into two part , one to satisfy the request and remaining (170 KB) is type of external fragmentation denoted by (170 KB E) .

Similarly for process B using 300 KB that results 120 KB E.

Similarly for process c using (170 KB E) results (40 KB E).

Similarly for process D using (130 KB) results (10 KB E) request of process E can't be completed **So total external fragmentation = 40 +10+120=170 KB**

**Total internal fragmentation = 50 + 150 + 70=270 KB**

# Answer
> 0 votes
NO! The Total Internal Fragmentation is 40 + 10 + 120 = 170kB And Total External Fragmentation is 50 +150 + 70 = 270kB

---
Tags: operating-systems, memory-management, memory-allocation
---


title: chromatic number is np-hard

text:
# Question
Title: chromatic number is np-hard
I'm referring to a question in this book: Algorithms by Jeff Erickson, link:http://jeffe.cs.illinois.edu/teaching/algorithms/notes/J-approx.pdf, in particular, pg.21, Q11.

The author mentioned that finding the chromatic number $\chi(G)$ is np-hard, and ask to show that return any integer between $\chi(G)$ and $\chi(G) + 31337$ is also np-hard. I believe the constant doesn't matter here, my approach is as following: given an instance of finding the chromatic number, we can modify it to finding $\chi(G)$ and $\chi(G) + c$, return an integer between $\chi(G)$ and $\chi(G) + c$.

From one suggestion seems like I'm having a wrong approach, any hint that helps me go further is appreciated.

# Answer
> 1 votes
No. Your reduction goes the wrong way. You will need to find a different proof.

It might be easy to find an algorithm that returns any integer between $\chi(G)$ and $\chi(X)+31337$, and hard to find an algorithm that returns exactly $\chi(G)$. (It isn't, but that isn't obvious, and you'll have to prove it.)

Analogy: it's easy for you to find an integer between my age and my age plus 31337, but I suspect it'd be hard for you to identify my age exactly. Try applying your proposed logic to this analogous situation, and hopefully you'll see what goes wrong.

---
Tags: algorithms, np-complete, reductions, np-hard
---


title: Getting rid of "FG" in a LTL equation

text:
# Question
Title: Getting rid of "FG" in a LTL equation
i am currently struggling with a Linear temporal logic equation: $$\phi=FG( \lnot a\lor X \lnot a )$$ For my understanding, it means that starting at a certain point in the future, proposition a can never be reached again due to the definiton of "finally globally".

Now we have to transform it into an aquivalent equation that only contains the "Until" (U) "Next" (X), $\lnot$ and $\land$ operator.

My first approach was "everything allowed until never a again" but for that i would need "F" or "g" again, or am i getting something wrong?

Thinking about this problem for quite some days now, my prof said it was pretty easy but i just cannot figure it out, i hope some of you guys can help me :D Thanks in advance! Enjoy your day :)

# Answer
> 1 votes
Not a full solution, but a guide: First, note that the meaning of $G$ is "always" (or "globally"), not "never". Thus, $FG$ means "from a certain point and on" (or in LTL phrasing: eventually always). The intuitive meaning of the formula $FG(\neg a\vee X\neg a)$ is that from somepoint and on, either you see $\neg a$ now, or in the next step.

However, all this is unnecessary in order to convert the formula to the temporal operator $U$ -- the operators $F$ and $G$ are built from $U$, and the translation is completely mechanical, using the following definitions:

* $F\phi=\text{true}U \phi$
* $G\phi=\neg F\neg \phi$

Simply apply these rules, and you'll have your formula.

---
Tags: model-checking, linear-temporal-logic
---


# Question
Title: What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?
I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an integer dataset. However, I am wondering if there are any other variables which I can modify, for example standard deviation, in the integer dataset itself that would be of any benefit to my comparison.

# Answer
Try these: Sorted. Reverse sorted. Two sorted halves. One half ascending, one half descending. Sorted with 0.1%, 1%, 10% random changes. Random. All values equal, 99% equal, 50% equal. Two different values only.

Unless you are 100% sure that one of these case cannot happen (and you are never 100% sure), all of these should run in a reasonable time. Some of them, like "Sorted" or "sorted with 0.1% random changes" can run much faster than others. If these cases are common, then you would want them to run faster.
> 1 votes

# Answer
The simplest is not doing a proper shuffle, that is having partially (reverse) sorted sequences, in extremis this can be the entire range is sorted except a few elements at the end that need to be inserted somewhere in the range.

For comparison sorts the distribution of elements doesn't make a difference, only how many duplicate values there are. This is something you can adjust as well.
> 0 votes

---
Tags: algorithms, sorting, binary-search-trees, data-sets, heap-sort
---


# Question
Title: Is integer multicommodity flow problem is NP-hard?
As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?

# Answer
> 2 votes
Integer multi-commodity flow is indeed NP-complete, as stated in the corresponding Wikipedia article (link to the reference paper).

However, your reasoning is incorrect. If ILP is NP-complete and some problem X reduces to ILP, it does not mean that X is NP-complete. In order to show NP-completeness of X via ILP (or any other NP-complete problem) you need to provide the reduction in the opposite direction — from ILP to X: that is, given an arbitrary ILP instance, convert it to a network such that finding the multi-commodity flow in that network will give the solution to the original ILP instance.

NB. Just to clarify: you can replace *NP-complete* with *NP-hard* in the above explanation. NP-completeness means both being NP-hard and belonging to NP, and showing the latter is trivial for mentioned problems.

---
Tags: time-complexity, np-complete, np-hard, integer-programming
---


# Question
Title: List of algorithms that depend on sorting / ranking / argsorting
I am looking for a list of algorithms that depends on sorting / relative ranking / argsorting, *not* for a list of sorting algorithms.

I want to study and illustrate the importance of fast sorting in other algorithms. I am looking for something rather exhaustive (or at least covering my - not so - niche field: data science). Any idea if that sort of list was formalized somewhere?

# Answer
> 1 votes
You probably checked this obvious reference already. I add it just in case: The Art of Computer Programming, Vol III sorting and searching, D. Knuth, Chapter 5, pages 1 to 5 provide an overview of sorting applications. These may lead to other sources discussing related algorithms that depend on sorting. The Huffman encoding algorithm starts with a sort on the character frequencies.

---
Tags: algorithms, reference-request, sorting
---


# Question
Title: How exactly is the process of showing a problem to be NP-Complete a proof by contradiction?
The steps involved in proving that a problem is NP-Complete are fairly straightforward to follow, it's the logic behind why the proof is valid that's really throwing me for a loop. Okay so an easy one: we are showing that 3SAT is NP-Complete. There are 2 things that must be shown. First we show that 3SAT is in NP and then we must show that it is NP-Hard. To show that 3SAT is NP we just show that a given solution can be verified in polynomial time. Now say we show 3SAT is NP-Hard using Circuit SAT. We find a polynomial time reduction from Circuit SAT to 3SAT. Then we show that an arbitrary solution to Circuit SAT gives us a corresponding solution for 3SAT and also show that if we're given the solution to a 3SAT problem that was generated by our polynomial time algorithm that we can also derive the solution to the corresponding Circuit SAT problem. That all seems fairly straightforward, but why does doing this allow us to conclude that 3SAT is NP-Hard and thus is NP-Complete?

# Answer
> 7 votes
1. There is no contradiction
2. NP-hard means that the problem is "harder than" all problems in NP.
3. We know that Circuit Sat is NP-complete.

We know that Circuit Sat is harder than all problems in NP. If 3SAT is harder than Circuit Sat, then 3SAT must also be "harder than" all problems in NP.

NP-complete is defined as NP membership and NP-hardness. You prove both, hence you've proved NP-completeness.

If you're still uncertain, go back to the definitions of NP and polynomial time reductions.

Check also the reference question What is the definition of P, NP, NP-complete and NP-hard?

# Answer
> 3 votes
# What is NP

A problem is in NP if, with a polynomial-length "magically provided" proof string for any given problem instance whose answer is "yes", can verify the answer is "yes". Equivalently, if you make a NDTM that accepts problems whose answer is "yes" in polynomial time. These are equivalent; the "proof string" can be treated as the set of choices the NDTM would take to reach the accept state. The "magically provided" bit because the NDTM tries *every path*, and if any one path accepts, we record that "proof string". A deterministic turning machine could take the description of the NDTM and the "proof string" and verify that the problem is accepted by the NDTM.

# What is NP-hard

A problem is in NP-hard if, given a polynomial time solution for it, you could solve *all* NP problems in polynomial time. In fact, it means you can "reduce" all NP problems to a problem in your NP-hard problem set in polynomial time. This means map the NP problem to an instance of your NP-hard problem in such a way that a solution to your NP-hard problem gives you the answer to your NP problem.

Now, once you have found one NP-hard problem X, you can "reduce" others to it. A reduction is when you take your problem set Y, and show that any problem in X can be mapped to a problem in Y in polynomial time in such a way that solving the Y problem implies the solution to the X problem.

If we have such a reduction, then any arbitrary NP problem into an X problem, then reduce *that* to a Y problem, and thus a P-time solution to Y problems is sufficient to solve any arbitrary NP problem in P-time.

# What is NP complete

NP complete is when something is both NP-hard and in NP. There are problems that are NP-hard but we know (or strongly suspect) are much harder than NP.

# Foundation

Now, almost all of the time when you prove something NP-complete, we reduce it to another problem.

At the base of all of this is some problem we proved to be NP-hard and in NP *without* reducing it to another problem.

The trick is we can carefully pick such a problem so that the proof is pretty much by definition. We defined membership in NP as either acceptance by an NDTM or by effectively a proof-checker ("certificate verifier" if you don't want to talk about proofs). Proving those two are equivalent isn't that hard.

All we have to do is take some more amenable and show it can solve a sufficiently powerful certificate verifying system in polynomial time.

What you end up with is a web of known NP-complete problems. Some of them are reduced with clever tricks, some of them are cleverly designed to be easy to reduce to. And instead of having to go all the way back to the definition of NP to show something is NP-hard, you can just reduce one of a library of known NP-complete ones to it to pull it off.

# Answer
> 2 votes
Take as given the following:

* Circuit SAT is NP-Complete (which means it is also NP-Hard)
* A problem is NP-Hard if and only if, for every problem in NP, there exists a polynomial time algorithm that converts it into the NP-Hard problem. This is the definition of NP-Hard.

Now, in your proof, you demonstrate that there exists a polynomial time algorithm that converts any Circuit SAT problem into a 3SAT problem. Consider the following algorithm:

1. Start with any problem in NP.
2. Convert the problem into Circuit SAT in polynomial time. This is guaranteed to be possible because Circuit SAT is known to be NP-Complete.
3. Use your polynomial time conversion algorithm to convert it from Circuit SAT into a 3SAT problem.

Doing two polynomial time algorithms in sequence takes polynomial time, so this algorithm runs in polynomial time. It also converts any problem in NP into a 3SAT problem. The ability to do that in polynomial time is the definition of NP-Hard, therefore 3SAT is NP-Hard.

---
Tags: np-complete, np-hard
---


# Question
Title: Fast and compact data structure for dynamic graphs
A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ may be represented in central memory as follows:

* an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V\[v\]$, each of these lists being represented as a dynamic array;
* another associative array $E$ gives, for any $(u,v)\in \mathcal{E}$, the index of $v$ in $V\[u\]$.

**This structure is very appealing if many graph updates (vertex and/or edge additions and/or removals) are performed.** Indeed, graph updates may be performed in constant time (details below), and the whole structure takes only linear space. In addition, testing edge presence is in constant time and parsing node neighborhoods is optimal.

The literature on dynamic graph structures is very rich (see examples below). **Yet, I can't find any (formal or empirical) analysis of this simple structure anywhere.**

Does anyone have a pointer to such a study? If not, is this because people focus on worst case complexity only, and avoid hash tables for this reason? or because they assume only few graph editions are performed? or because it is considered too space costly? ...

---

**Linear time updates are obtained as follows:**

* adding vertex $x$ is just adding the key $x$ to the associative array $V$, with an empty dynamic array as associated value;
* removing vertex $x$ is just removing key $x$ from the associative array $V$ (assuming it has no edge at removal time);
* adding edge $(x,y)$ is just adding $y$ to the end of the dynamic array $V\[x\]$ and setting $E\[x,y\]$ to the correct value, $len(V\[x\])-1$;
* removing edge $(x,y)$ is slightly more subtle if $x$ has more than one neighbor; it consists in moving the last element $z$ of $V\[x\]$ to the position of $y$ and removing the last element of $V\[x\]$, which may be done efficiently thanks to the associative array $E$:

0. $z \gets V\[x\]\[len(V\[x\])-1\];$
    1. $V\[x\]\[E\[x,y\]\] \gets z;$
    2. $E\[x,z\] \gets E\[x,y\];$
    3. remove last element of $V\[x\]$;
    4. remove key $(x,y)$ from $E$.

Operations on dynamic arrays are in $O(1)$ amortized time, and operations on associative arrays (*i.e.* hash tables) are in $O(1)$ expected time. Therefore **all operations above are in constant time**. Testing edge existence is in constant time too (hash table access), and one may also optimally parse the neighborhood of any vertex (it is an array). In addition, the whole data structure needs **linear space** $O(|\mathcal{V}|+|\mathcal{E}|)$ only, as hash tables and dynamic arrays do.

---

**The literature on dynamic graph representations** does not seem to consider the structure above, see for instance:

Likewise, popular graph libraries do not seem to use this data structure, even performance-oriented ones that allow graph updates, like Networkit.

# Answer
Your data structure is a variant of the following standard data structure to represent a graph:

```
edges: Map[V, Set[V]]

```

where `V` is the type of vertices. That is, for each vertex, we store the set of adjacent vertices in a set. The map and set can be implemented as hashtables, so this is a hashtable of hashtables.

## Sources (sorry I don't have more!)

I did a bunch of digging through textbooks, Wikipedia, and implementations, and admit I am baffled that this representation does not seem often covered. So, I asked a separate question about it here. This is a related question, where the top answer suggests using the above representation. I did find the following *brief* mentions:

## Comparison to your representation

Your representation differs in that you store the incident vertices as a dynamic array, rather than as a set. But the dynamic array (together with your edge map $E$ to recover the index in the dynamic array from the edge name) is not really necessary. Instead of having $E$ to recover the index, above we store the incident vertices by label directly rather than by index.

The above supports all the operations you support in constant time: adding a vertex, removing a vertex, adding an edge, removing an edge, and checking edge existence. It also uses linear space. If a directed graph is desired, we can have two maps, `fwd_edges: Map[V, Set[V]]` and `bck_edges: Map[V, Set[V]]` to allow iterating over either forward or backward edges.

I don't think that your representation is fundamentally different from the above, but I do like your careful development of the map $E$ and I would be curious to see if you can show formally whether or not it is equivalent to this representation.

## Other variations

By the way, you may be interested in important variations of adjacency lists. One variation is if you want to support quickly *merging* vertices. Merging two vertices as array lists or sets is not possible efficiently, but for some dynamic graph algorithms we need $O(1)$ merge. For this, researchers use a union-find data structure to merge the vertex labels, and instead of `Set[V]` or your dynamic array, vertices are stored using a linked list. Linked lists can be merged in $O(1)$, so everything remains $O(1)$ except, unfortunately, checking for existence of an edge and deleting an edge, which require iterating over all possible edges. See for example, *A New Approach to Incremental Cycle Detection and Related Problems,* Bender, Fineman, Gilbert, Tarjan, 2015 for such a data structure in use.
> 1 votes

---
Tags: graphs, data-structures, reference-request, online-algorithms, streaming-algorithm
---


title: Reducing one problem to another

text:
# Question
Title: Reducing one problem to another
I know this is sort of a basic question, but I don't completely understand the following. Let $A$ and $B$ be two problems. If I take one instance $a$ of $A$ and one instance $b$ of $B$, and show the following. Solving $a$ implies solving $b$, and solving $b$ implies solving $a$. Am I showing that $A$ reduces to $B$, $B$ reduces to $A$ or both? How are $A$ and $B$ related using the $\leq\_P$ and $=\_P$ notation?

# Answer
> 1 votes
Neither -- you can't show a reduction by starting out with an instance of $A$ and an instance of $B$. Instead, a reduction has to be a way of *transforming* instances of $A$ into instances of $B$, and vice versa.

A reduction from $A$ **to** $B$ means you give a way of transforming any instance $a$ of $A$ **to** an instance $f(a)$ of $B$, such that $a$ is a yes-instance of $A$ if and only if $f(a)$ is a yes-instance of $B$. Here $f$ is the reduction, or transformation. Notice that $f(a) = b$ might not just be any instance of $B$, but it might be a very particular instance constructed by our transformation.

For example: suppose $A$ is the problem of determining if a number is even, and $B$ is the problem of determining if a number is a multiple of 10. Then to give a reduction from $A$ to $B$ we could start with a number $n$, and multiply it by $5$. Our reduction is:

```
f(n) = n * 5

```

This is a valid reduction because `n` is an even if and only if `n * 5` is a multiple of 10. But, it doesn't construct every possible instance of $B$; only multiples of $5$ are actually constructed as instances of $B$, not all integers.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Is there a simplistic way of describing the proof to the undecidability of David Hilbert's 10th problem?
I recently have been reading a bunch about David Hilbert's famous 10th problem, and trying to understand its proof. I am currently in the process of reading through an explanation of the proof, given by one of the people involved in trying to solve the problem, Martin Davis, Ph. D. It is really well explained, but pretty long.

Therefore I wonder, is there an easy/short way to explain the proof, albeit by simplifying some of its points, and skipping proving some minor components of the general proof?

Thank you in advance

# Answer
The question in the title is subjective, but I suspect no. Hilbert's 10th is one of the most important, but also one of the most complex, results of the last century. The proof itself spans 21 years of research by 4 mathematicians. If the majority of the proof isn't "easy" from Davis's text, I don't know if we can hope for something simpler.

However, there are good expositions of the structure of the proof. It has now been fully formalized (as of 2019), which would be one place to investigate to understand the proof's components. You may find the following paper useful:

* *Hilbert’s Tenth Problem in Coq.* Dominique Larchey-Wendling and Yannick Forster. FSCD 2019. Link

The introduction to the paper gives a nice overview of the history of the proof, and the structure that was chosen for the formalization effort. An excerpt: the authors show that \begin{align\*} \mathsf{Halt} &\preccurlyeq \mathsf{PCP} \preccurlyeq \mathsf{MM} \preccurlyeq \mathsf{FRACTRAN} \\ &\preccurlyeq \mathsf{DIO}\_{\mathsf{FORM}} \preccurlyeq \mathsf{DIO}\_{\mathsf{ELEM}} \preccurlyeq \mathsf{DIO}\_{\mathsf{SINGLE}} \preccurlyeq \mathsf{H10} \end{align\*}

So understanding the proof is just a matter of understanding each of the 7 reductions above.
> 4 votes

---
Tags: computability, sets, number-theory, polynomials, diophantine-equation
---


title: Is this set covering problem NP-Hard?

text:
# Question
Title: Is this set covering problem NP-Hard?
Consider this variant of set covering problem.

Input: a collection of sets $S = \\{s\_1, s\_2, \ldots, s\_n\\}$ and a universal set $U$, in which $s\_k \subseteq U$ for all $k$.

The problem is, divide $S$ into two subcollections $S'$ and $S''$ (i.e. $S' \cup S'' = S$, $S' \cap S'' = \emptyset$) to maximize $|U'| + |U''|$ where $U'$ is the union of all sets in $S'$, and $U''$ is the union of all sets in $S''$.

Is the above problem NP-Hard?

# Answer
**This problem is NP-Hard**.

Consider a decision problem of this problem: Whether there exists a partition of *S*, such that |*U'*| + |*U''*| = 2|*U*|? This problem is equal to the problem of 2-DSC, which has been proved to be NP-Complete in paper https://link.springer.com/article/10.1007/s11276-005-6615-6. (Cardei M and Du DZ. "Improving wireless sensor network lifetime through power aware organization." Wireless networks 11.3 (2005): pp333-340.) Thus, this problem is NP-Hard.
> 3 votes

---
Tags: np-complete, np-hard, sets, subset-sum
---


# Question
Title: I want to determine if this language is non regular-any tips?
After working through some examples of proving the non-regularity of languages I encountered this language

$$ L = \\{(ab)^{i}a^{j} | i \geq j, i,j \in \mathbb{N}\\} $$

Where $a^{k}$ = a repeated k times. Is this language regular? I believe not since there are infinitely many strings $(01)^{i}$ with $i \geq j$, so a DFA or NFA cannot accept the language

# Answer
A regular language can be recognised by a finite state machine.

After processing (ab)^i and (ab)^i’, i ≠ i', the state machine must be in different states: If say i \< i’, and j = i’, then (ab)^i a^j is not in the language, but (ab)^i’ a^j is, so processing a^j from both states must end in different states, one not accepting, one accepting.

Since i, i’ were arbitrary there cannot be a finite number of states.
> 3 votes

---
Tags: regular-languages
---


# Question
Title: Runtime analysis with multiple parameters: case study with heaps in Huffman coding
While studying a book on algorithms, I came across a question that asked about essentially $d$-ary Huffman coding, where the codeword alphabet has $d$ symbols (the usual case has $d=2$, with symbols $0$ and $1$, ie, binary).

Adapting the usual Huffman coding algorithm for the $d$-ary case is simple enough, and things work as expected. However, it had me thinking on whether or not choosing a different data structure could improve the running time.

The question rises very naturally, since traditional binary Huffman uses a binary heap. Could it perhaps be that using a $d$-ary heap for $d$-ary Huffman would result in better runtime complexity?

I've tried my hand at it and calculations get ugly very fast. The worst part, however, is the fact that I'm having a very hard time actually proving anything in the direction of optimality when big-O is involved. Since big-O can discard so much of an expression, I'm finding it difficult to handle it when more than one parameter is involved.

In this particular case, we have three parameters:

* $n$, the size of input
* $d$, the size of the code-word alphabet
* $k$, the type of heap used ($k$-ary heap)

The calculations seem to suggest that $k=3$ and $k=4$ should, theoretically, always outperform the binary heap, regardless of the value of $n$ and $d$. Indeed, *a posteriori* this seems to be something intrinsic to the heap structure.

However, a choice between these values, or a demonstration that higher values of $k$ are suboptimal, still seems elusive; and in this case the context (algorithm, values of $n$ and $d$) should play a role.

# Answer
You use a priority queue. Priority queues are usually implemented using a heap. That can be a binary or some other heap, but that decision has nothing whatsoever to do with your Huffman code implementation.

And there is no change in Big-O behaviour, just in the constant factors, which are implementation dependent.

But in the end, the time to build the code is negligible compared to the time needed to compress or decompress a large file.
> 1 votes

---
Tags: runtime-analysis, heaps, parameterized-complexity, huffman-coding
---


title: Algorithmic Problem on Trees

text:
# Question
Title: Algorithmic Problem on Trees
Given a directed, rooted tree with $n$ vertices, the height of a vertex $v$, $h\[v\]$ is the number of edges on the longest path from $v$ to some reachable leaf node. Give an efficient algorithm to find the following,

$ d\[v\] := \max\limits\_{w \text{ is a sibling of $v$}} h\[w\] \qquad \forall v \in V. $

Note: The algorithm I was able to come up is the trivial one.

1. Finds the height of all vertices using DFS.
2. Do a BFS from the root and store all the vertices to a particular distance in a map.
3. Go over the list for every element $v$ and find the maximum using the expression above.

Can we do better than this?

# Answer
> 2 votes
The basic idea in your algorithm is correct (it will result in an optimal algorithm if you implement it correctly)

Hpwever the details are missing. For example, how can one compute the height of the nodes using DFS?

Another important detail is the "mapping" you talked about. How exactly do you store this mapping? The regular approach of using a hashmap will not do the job well enough. You may want to consider storing it as a list of lists (think about it for a minute, it shouldnt be too complicated) instead.

---

Now to the main question - this algorithm is optimal. The runtime of each step is $O(n)$, and thus the entire algorithm takes $O(n)$.

But notice that the problem requires you to output a value for each node - and thus *any* algorithm will have to spend at least $\Omega(n)$ time printing the output.

---
Tags: algorithms, graphs, trees
---


title: DPDA by empty stack

text:
# Question
Title: DPDA by empty stack
Let's say we have DPDA with acceptance by empty stack, *w* is accepted by this DPDA. Why can't *wv* be accepted? I know about the prefix property but i don't see where it's coming from. Can't we just continue moving after reading *w* when the stack is empty until we read the whole input and decide whether we accept the word by looking at the stack state?

# Answer
A transition in a PDA always needs to read a symbol in the stack. If there is no symbol, there is no transition.

Since the PDA is deterministic, reading $w$ will **always** reach a configuration with an empty stack, and no transition can permit to read any non empty word.
> 1 votes

---
Tags: formal-languages, pushdown-automata
---


# Question
Title: Is the right quotient of a regular language respect to another regular language a regular language?
Will the language $\\{w\in L\_1\mid \exists v, wv\in L\_2\\}$ be regular if $L\_1$ and $L\_2$ regular languages?

# Answer
> 0 votes
The prefix language of $L$ is the set of all prefixes of strings in $L$, $\\{w\mid \exists v \in \Sigma^\*, wv\in L\\}$. In other words, it is the right quotient of $L$ with $\Sigma^\*$, so it is certainly regular if $L$ is regular, by closure with right quotient.

A possibly simpler way to see this is to observe that you can construct a recogniser for the prefix language of $L$ by constructing the minimal DFA for $L$ and then making all states accepting.

Your language is the intersection of $L\_1$ with the prefix language of $L\_2$. Since regular languages are also closed with intersection, it must be regular if $L\_1$ and $L\_2$ are both regular.

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


# Question
Title: Combinatorics - how many $c$-distinct sets are possible?
I'm not sure if CS SE is the right place for this question, but since originally this question was in the CS area (and I translated it to a mathematical form), I will post it here.

I am given two parameters $m\in\mathbb{N}$ and $\frac{1}{2}\< p\le 1$, and I want to find the maximal value $k\in \mathbb{N}$, such that there are $A\_1,\dots,A\_k\subseteq \[m\]$ for $\[m\]=\\{1,\dots,m\\}$ and, we have the two following properties:

1. For every $1\le i\le k$, we have $|A\_i| \ge p\cdot m$
2. For every $i\neq j$, we have $|A\_i\cap A\_j|\le (1-p)\cdot m$

Essentially, I'm trying to find the maximal number of sets with size $p\cdot m$, who are $c$-far from being distinct in pairs, where $c:=(1-p)\cdot m$.

Equivalently, I'm interested in finding for every $k$ what is the highest $p$ with this property.

---

## My attempt

I tried to think of an approach similar to one where $p=1$, and the sets would be completely disjoint, therefore every $A\_i$ would add an additional $p\cdot m$ new elements, and thus $k=\frac{m}{p\cdot m}=\frac{1}{p}$. But this approach didn't work for me, since even if I say each set adds an additional $p\cdot m - (1-p) \cdot m = (2p-1)\cdot m$ new elements to every other set, I can't guarantee those elements are not in other sets.

---

## Some (additional) thoughts

After thinking additionally a bit, I think that one thing that would suffice for me is to show that the solution doesn't depend on $m$.

This is because in my usage of this problem, I actually try to find a $k$ such that this property **won't** hold, and I can choose my $k$ to be arbitrarily large *but* it would also increase $m$ arbitrarily. So - if the solution here won't depend on $m$, I don't need to worry about increasing $m$ arbitrarily.

# Answer
This is a partial answer for $p \> \frac{\sqrt{5}-1}{2} \approx 0.618.$ As Yuval Filmus points out in the comments, we are looking for the maximum number $k$ of binary codes with length $m$, weight $w = pm$ and pairwise distance at least $d = 2(2p-1)m$. If $p\>2/3$ then $k\leq 1$.

Now let $\lambda = w-d/2$. Equation (3) in \[1\] tells us that if $w^2\>\lambda m$ (which is the case when $p \> \frac{\sqrt{5}-1}{2}$), then $$k \leq \frac{m\cdot d/2}{w^2-\lambda m}.$$ This works out to $$ k \leq \frac{2p-1}{p^2+p-1}.$$

In particular for the case which seems to interest you the most ($p=2/3$) this gives an upper bound of $k\leq 3$ (which is easily seen to be tight).

I wasn't able to apply the other formulas in \[1\] to get anything subexponential in $m$ when $\frac{1}{2} \< p \leq \frac{\sqrt{5}-1}{2}$, but I applied the bounds very crudely, so it might be possible (might even be easy).

\[1\] Selmer Johnson, Upper Bounds for Constant Weight Error Correcting Codes, 1972.
> 1 votes

---
Tags: combinatorics, sets
---


# Question
Title: Sorting algorithm which sorts half the possible inputs in linear time
> Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time. (For the other half the algorithm can return anything, even a completely unsorted array.)

I know that using comparison model of sorting algorithms there is a lower bound of $\Omega(n \log n)$ so I try to make a proof by contradiction and to get to the fact that if such an algorithm exist then we can sort by comparison sort in linear time.

# Answer
Suppose that a comparison-based sorting algorithm sorts the set of permutations $\Pi$ correctly. Construct the comparison decision tree underlying the algorithm, with permutations as leaves. Each permutation in $\Pi$ must appear as a leaf (why?), hence the tree must have depth at least $\log\_2 |\Pi|$ (why?).
> 1 votes

# Answer
There are n! possible permutations of n items, which is why we need $\log\_2(n)$ comparisons, rounded up to the next integer since we can't have half a comparison, to distinguish them. That number is quite close to $n \cdot \log\_2(n / e)$. To sort half of the possible inputs, we need ONE fewer comparison. To get to linear time, we have to restrict the number of inputs a lot more.

On the other hand, we can sort an array for example in 100n comparisons when $\log\_2(n / e) \< 100$ or $n/e \< 2^{100}$ or $n \< e \cdot 2^{100}$. The largest computer that I can't afford to buy would sort any array that I could store in memory in 40n comparisons.
> 0 votes

---
Tags: sorting, lower-bounds, comparison
---


# Question
Title: 3SAT: Get smallest number of algorithm invocations to get a satisfiable assignment? How should it be done?
My Question is, what is meant with smallest number N. Does it mean I should try every possible constellation of the n variables and put each one of them into the formula φ and then use 3Sat on that? Then it would be 2$^{n}$? Is that meant?

# Answer
> 2 votes
You could try every possible assignment but you can do better.

Think about how you solve this problem recursively: Given bits $x\_0^\* \ldots x\_i^\*$ and we have that $\varphi(x\_0^\*, \ldots x\_i^\*, x\_{i+1} \ldots x\_n)$ is satisfiable for some $x\_{i+1} \ldots x\_n$. Now you just need to determine whether $\varphi(x\_0^\*, \ldots x\_i^\*, x\_{i+1}^\*, x\_{i+2} \ldots x\_n)$ is satisfiable if you fix $x\_{i+1}^\*=1$ or $x\_{i+1}^\*=0$, which gives you bits $x\_0^\* \ldots x\_{i+1}^\*$.

Can you take it from here?

# Answer
> 2 votes
You are given a machine which solves SAT. You can give it any formula $\varphi$, pay a fee of \\$1, and then it immediately tells you whether $\varphi$ is satisfiable or not.

Using this machine, you want to find a satisfying assignment for a formula $\psi$ on $n$ variables which is promised to be satisfiable. How much would it cost you, using the optimal strategy? (You're trying to minimize the cost, which is the same as minimizing the number of invocations of the machine.)

---
Tags: 3-sat
---


# Question
Title: How can we prove that a reduction exists?
**Problem:** I have two computational problems, $A$ and $B$. We know that $A \in \texttt{Psearch}$ and I want to prove that $A \leq\_p B$ for all problems $B$.

**Goal:** It is my understanding that my goal is to prove that there is a polynomial time reduction $R$ from $A$ to $B$ given that $A \in \texttt{Psearch}$.

I know from lecture that if $A \leq\_p B$ and $B \in \texttt{Psearch}$, $A \in \texttt{Psearch}$. How do you go from knowing $A \in \texttt{Psearch}$ to $A \leq\_p B$?

# Answer
**Hint:** What does it mean that $A\in P\_{search}$? What knowledge does that give us on $A$? Now, try to use this knowledge to directly construct a reduction from $A$ to $B$. Notice that we don't really need $B$: this property is entirely proven from the information we know about $A$.
> 1 votes

---
Tags: reductions, polynomial-time-reductions
---


# Question
Title: Real life examples of *zero* weight edges in graphs
The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously.

Yet, when I recently read here a question on real life example of graphs with *negative* weight edges I was amazed I never asked this one before:

**Does anyone know a meaninfgul example of weighted graph where edges with zero weight make sense (other than non-existing edges)?**

Negative weights may be allowed, but I would prefer cases where only positive weights are allowed, including zero weights.

# Answer
> 25 votes
Of course. The weight can *mean* things that are irrelevant to the existence of an edge.

Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one.

Consider a road network. If you want to find a path from A to B in a road network, you need to keep all the road segments that exist. There are two important measures:

* Current amount of traffic
* Additional costs for that specific path

That is, how quickly can we go from A to B, and how much does it cost.

* Many roads have zero traffic at a given time, and you shouldn't delete the road segment.
* Many roads have zero incurred cost, you should not delete these either.

Of course, you can change $t$ to be for example (as in the linked question) steepness, or other things like *congestion*, expected delays, or whatever else, e.g. "toll road cost" or expected number of trolls. The point is that the edge in itself is important. And many road segments have properties that can be explained with a zero.

# Answer
> 12 votes
The classic strategy game *Civilization* by MicroProse represents the world map as a square grid where each node of the grid is a tile of the world map, representing some type of terrain. Players control civilian and military units over this map. Each unit has a specific allocation of movement points, and each terrain type costs a specific amount of movement points to traverse, sometimes depending on the unit type. For example, an armor unit may be able to move three tiles on a plain, but only one tile on a mountain. Due to the variable terrain cost for movement, pathfinding in this model can be conceived as a shortest path search in a weighted graph.

The game allows the construction of roads and railroads to facilitate the deployment of units. A railroad segment is constructed within a single tile at a time and renders movement completely free between two adjacent tiles containing a railroad segment each. For the purposes of pathfinding, tiles with this kind of railroad connection can therefore be treated as setting the edge weight between them to zero.

# Answer
> 9 votes
In circuity, we often construct a graph of a circuit. Wires are typically modeled as 0 resistance because, frankly, measuring the resistance of wires is really tricky and rarely profitable. So if we have multiple devices connected to a single wire, we can treat that as separate vertices with 0 weight nodes between them.

We can transform them into one "supernode." Indeed, in many analyses we do so. However, the first step is almost always to get a graph with 0 weight edges, and then transform it.

This also has the advantage that, when we short a circuit and suddenly have to care about that minuscule resistance of each wire, the circuit we analyze is trivially comparable to the one we started with.

# Answer
> 4 votes
Such a graph does not need to represent an actual road network. It can be anything representable by a network. For example, conversion options between various online banking and cryptocurrency services. Most of them have a little or more fee, but sometimes you can do it for free (most likely, internal conversions by the same service, like sending cash from your bank account to your credit card account).

If you want to buy bitcoin from the money on your bank account, the cheapest way is often not some direct service. This is yet more complex if you are also trying to speculate with bitcoin, and not only store cash in it. Finding the optimal way is a graph walking process where some edges have zero price.

# Answer
> 3 votes
### Distances and times (and other units of measurement)

Consider a graph where the edges are the driving distances between warehouses across the country. If two warehouses are on the same premises, they could potentially be given a distance of 0. Strictly speaking there might be some distance between them, but this may be considered negligible if the distance is small enough or if you can transport the goods without actually having to drive from one to the other.

Why not just merge those into one vertex? Wouldn't all the outgoing and incoming edges be duplicated? Not necessarily. If different warehouses serve different purposes, it could be reasonable for those 2 warehouses to be connected to different sets of other warehouses.

---

Or consider some arbitrary process flow graph (e.g. the general flow of processes and equipment inside a factory) with various tasks which each generally take a few days to complete, where the edges represent time.

Now consider a task that can be run in a few milliseconds on a computer. Under the right circumstances, one could reasonably just assign this an edge weight of 0.

As above, you may want to keep the vertices which have a 0-weight edge separate, because this can provide some visibility about the additional process and better reflect the real world, and the vertices can again be connected to different subsets of other vertices.

# Answer
> 2 votes
**Neural networks**

A neural network assigns weights to each connection between the simulated neurons. As you say, when calculating the output of the network, any edges with zero weight are equivalent to missing connections.

However, the training step considers both the weight of the edge and the partial derivative of the output value with regards to the weight. In other words: to adjust the weight of each edge, the training algorithm calculates how much the change affects the output. If the edge was truly missing, it could never get a weight other than 0.

# Answer
> 2 votes
Not sure if this is a stretch for this question, but an NFA for the regex `(xx)?` is

```
          ϵ
[Start] ─────→ [Accept]
   │              ↑
   └───── xx ─────┘

```

It's not technically a number, but semantically the ϵ edge is a "null"-weighted edge: you can take it without incurring any "cost" (which in this case might be consumption of characters).

So if you wanted to make an NFA for a regex (which you might, if e.g. the DFA is too large), you might end up with a transition like this.

# Answer
> 1 votes
## Airport terminals

(That's an interesting question and kind of a nice brain-teaser. I haven't seen the answers given in the other question, so I might be duplicating something)

Imagine a graph of world's international airport routes with:

* each terminal being a vertex
* each edge being a flight connection with scheduled flight time as its weight

Then quite naturally you would like to model two terminals of the same airport to be two distinct vertices, but the edge between being of `0` weight (as there's no flight time involved to move between them).

# Answer
> 1 votes
Consider a road network that consists of segments of toll roads, with a fixed toll for each type of vehicle on each segment.

So we represent the road network as a graph and to work out the cost of a path add up the cost of the links in the path. However some links don't have tolls for bike, hence will have a zero cost.

If we removed these zero cost links from the graph for bikes, then we would need a seperate copy of graph for each vehicle type. This would then need many graphs to be edited whenever a road was changed.

---

Also if you ever work with real life map data you will find roads of zero length that can't be removed from the published data for practical reasons.

# Answer
> 1 votes
Three computers (nodes a, b, and c) networked together (edges) with the amount of traffic between the each node the weight, in MB.

```
(a) <-- 50MB --> (b) <--+
 ^                      |
 |                     10MB
 |                      |
  \-- 0MB --> (c) <-----+

```

Here the edges are a\<-\>b, b\<-\>c, and a\<-\>c with weights 50, 10, and 0. Negative weights are meaningless in this example -- a directed graph measuring traffic in each direction might be appropriate.

A previous comment mentioned roads. Maybe the weight is the number of cars per hour and maybe between 2:00AM and 3:00AM there were zero cars. The road didn't disappear, it just wasn't used.

# Answer
> 0 votes
An video game example.

Take a game where raw resources are processed into more complex items. For example, Wire can be made from copper, but it can also be made from Iron.
The game does not differ between Regular Wire and Iron Wire (they are the same thing), hence edge weight of 0.
However, it is organizationally advantageous for player to consider them separate nodes, because of iron and copper availability in the area.

---
Tags: graphs, terminology, discrete-mathematics, weighted-graphs, matrices
---


# Question
Title: Boolean circuit size bounds on the majority function
I am a bit lost in the literature. Is it known whether there is a $o(n \log n)$ size boolean circuit family for the majority function?

# Answer
> 3 votes
A binary full adder takes as input three bits $x,y,z$, and outputs two bits $a,b$ such that $x+y+z = 2a+b$.

Now suppose we are given $2^n$ bits $x\_1,\ldots,x\_{2^n}$. We compute as follows:

* $x\_1 + x\_2 = 2a\_1 + b\_1$.
* $b\_1 + x\_3 + x\_4 = 2a\_2 + b\_2$. Thus $x\_1 + x\_2 + x\_3 + x\_4 = 2(a\_1 + a\_2) + b\_2$.
* $b\_2 + x\_5 + x\_6 = 2a\_3 + b\_3$. Thus $x\_1 + \cdots + x\_6 = 2(a\_1 + a\_2 + a\_3) + b\_3$.
* ...
* $b\_{2^{n-1}-1} + x\_{2^n-1} + x\_{2^n} = 2a\_{2^{n-1}} + b\_{2^{n-1}}$. Thus $x\_1 + \cdots + x\_{2^n} = 2(a\_1 + \cdots + a\_{2^{n-1}}) + b\_{2^{n-1}}$.

Using $O(2^n)$ gates, we computed $2^{n-1}$ bits $a\_1,\ldots,a\_{2^{n-1}}$ and a bit $b\_{2^{n-1}}$ bits such that $$ x\_1 + \cdots + x\_{2^n} = 2(a\_1 + \cdots + a\_{2^{n-1}}) + b\_{2^{n-1}}. $$ Thus $b^{2^{n-1}}$ is the LSB of the sum $x\_1 + \cdots + x\_{2^n}$, and the higher-order bits of the sum are just the sum $a\_1 + \cdots + a\_{2^{n-1}}$. In particular, the majority of $x\_1,\ldots,x\_{2^n}$ is the same as the majority of $a\_1,\ldots,a\_{2^{n-1}}$. This gives a recursive circuit for majority whose size satisfies the recurrence $$S(N) = S(N/2) + O(N), $$ whose solution is $S(N) = O(N)$.

If implemented carefully, the circuit size is roughly $5n$. Demenkov, Kojevnikov, Kulikov, and Yaroslavstev improved this to roughly $4.5n$ in their paper New Upper Bounds on the Boolean Circuit Complexity of Symmetric Functions.

---
Tags: circuits
---


title: Letting the computer decide the outcome

text:
# Question
Title: Letting the computer decide the outcome
I have exactly no knowledge of programming. I want to design/develop/etc a video game I've been wanting to do and part of this is a crafting system similar to what Skyrim has.

Let's say we are working on making an edible food or drink. I want the character to be able to mix ANY ingredient to create a food or drink or even potion. But I don't want there to necessarily be a set outcome. I want the computer to be able to read the information of several ingredients and let the computer decide what the effects of the created product will be.

For example: The player would grab several totally random seemingly unrelated ingredients, and when mixing the ingredients to create a usable object the computer would then read those things and decide the effects. Once the potion/food/drink/poison is created it is a learned recipe.

What would the code for that even look like?

# Answer
> 1 votes
Use pseudorandom numbers to randomize those elements.

---
Tags: algorithms
---


# Question
Title: A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable?
1. if A be an NP-complete problem, and if B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable?
2. on the contrary, if A be an NP-complete problem, and B be an NP-hard problem. If A is polynomial time solvable then is B is polynomial time solvable?

My intuition is, (which may be very wrong), for (1) there are some problems, which are not in NP but are still NP Hard. In that case, wouldn't that make the first statement false? Since a basic requirement for a problem to be in NPC is that the problem should belong to NP Hard first.

# Answer
When you hear B is NP-hard, you can consider B being undecidable. If P = NP, then B is still undecidable.

If A is NP-complete and B is NP-hard, and B polynomial time solvable, then, yes, recall:

* if X is NP-hard, then for every problem Y in NP, there exists a polynomial time reduction from Y to X.

It follows that then A must be polynomial time solvable too.
> 1 votes

---
Tags: np-complete, np-hard, np
---


# Question
Title: Edge included in all the minimum spanning tree if it is included in at least 2 minimum spanning tree
Is it true that if an edge is included in at least two different minimum spanning tree, then that particular edge is included in all minimum spanning tree? If so why?

# Answer
> 1 votes
Consider $C\_3$, the cycle on three vertices. List all its MSTs.

---
Tags: graphs, minimum-spanning-tree
---


# Question
Title: Star notation for context-free language alphabet?
I noticed that some "design-the-grammar" problems say verbally

> Alphabet is $\mathbf{\\{0,1\\}}$.
>
> $\\{w \mid w \text{ contains at least three 1s}\\}$

and some problems list it as

> $\\{ w ∈ \mathbf{\\{0,1\\}}^\* \mid w \text{ contains at least three 1s} \\}$

So, my question is: Is the in-line notation with the asterisk star '\*' (as in "$\\{0,1\\}^\*$") equivalent to saying "alphabet is $\\{0,1\\}$", or are those alphabets different?

# Answer
> 2 votes
It is equivalent (usually, otherwise it would be explicitly stated).

The "star-operation" is called a Kleene-star, and it is an operation that basically takes the set and creats the set of all combinations of items from the original set. In the example of $\\{0,1\\}$, we would have that $\\{0,1\\}^\*=\\{0^{k\_1}1^{k\_2}0^{k\_3}\dots\mid k\_1,k\_2,\dots\in \mathbb{N}\\}$, and intuitively speaking, this is the set of all words created from the alphabet $\\{0,1\\}$. This obviously is also true for any other alphabet $\Sigma$ you would want.

# Answer
> 2 votes
There are two different ways to define languages:

* A language over an alphabet $\Sigma$ is a collection of words over $\Sigma$.
* A language is a collection of words.

While we often think of a language informally just as a collection of words (without an underlying alphabet), the usual definition of finite automata does specify an alphabet, and so the language of an automaton always has an alphabet associated with it.

When we write $L = \\{ w \in \\{0,1\\}^\* \mid \cdots \\}$, we mean that $L$ is a language over the alphabet $\\{0,1\\}$ consisting of all words such that "$\cdots$". This is just a conventional way to describe the alphabet that the language is defined over.

---

Wikipedia implicitly uses the first definition. If we want to make the definition more formal, we would define a language as a pair $(L,\Sigma)$, where $\Sigma$ is an alphabet (a non-empty finite set) and $L$ is a subset of $\Sigma^\*$ (the set of all words over $\Sigma$).

While formally a language is a pair $(L,\Sigma)$, often the alphabet $\Sigma$ is understood from context, and we only talk about $L$. This is the same convention used in abstract algebra, where the underlying set stands metonymically for the entire algebraic object.

Given just a collection of words $L$, it is impossible to completely reconstruct $\Sigma$. For example, the empty language can be viewed as a language over any alphabet, the language $\\{0^n : n \geq 0\\}$ can be viewed as a language over any alphabet containing the symbol $0$, and so on. The notation $L = \\{w \in \Sigma^\* \mid \cdots\\}$ usually suggests that the underlying alphabet is $\Sigma$, but it is not necessarily used consistently in this way.

In most circumstances, not much is lost by not specifying the underlying alphabet explicitly. I suggest ignoring such niceties whenever possible.

# Answer
> 1 votes
The other answer gives, I think, a slightly non-standard definition of the Kleene-star which doesn't emphasise that $\\{0,1\\}^\*$ is the set of all *finite* strings whose characters are all $0$ or $1$.

For an alphabet $\Sigma$, you can define $\Sigma^\*:=\Sigma^0\cup\Sigma^1\cup\Sigma^2\cup\cdots$, where $\Sigma^i$ is the set of strings of length $i$ with characters from $\Sigma$. (Formally, $\Sigma^0:=\\{\epsilon\\}$, where $\epsilon$ is the empty string, and for each $i\in \mathbb{N}$ we define $\Sigma^{i+1}:=\\{wx:w\in\Sigma^i\land x\in\Sigma\\}$.) Notice that the empty string, $\epsilon$, is contained within the set as it is in $\Sigma^0$.

If you've got a mathematics background, you might think of this as the "free monoid over $\Sigma$".

In the case you give, yes, the two definitions are therefore the same.

# Answer
> 0 votes
Formally, the version of

> $\\{ w ∈ \mathbf{\\{0,1\\}}^\* \mid w \text{ contains at least three 1s} \\}$

does not really say anything about the alphabet of the language. It might be {0,1}, but might also be bigger. Only the (part of the) alphabet, from which the desired strings are constructed is specified.

So while the language specified is the same, its complement might differ. Over an alphabet {0,1,2} the complement would include all strings containing a 2, while over the alphabet {0,1} these do not even exist.

Thus the two statements are not really equivalent in general, although in a context, where the alphabet is already set to {0,1} they are.

---
Tags: formal-languages
---