# Question
Title: Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead?
**First Slide: Find Max(A)**

1. // INPUT: A\[1..n\] - an array of integers
2. // OUTPUT: an element m of A such that m \>= A\[j\], for all 1 \<= j \<= A.length
3. max = A\[j==1\]
4. for j = 2 to A.length
5. if max \< A\[j\]
6. max = A\[j\]
7. return max

**Second Slide: Proof By Contradiction**

Proof: Suppose the algorithm is incorrect. Then for some input A, either:

1. max is not an element of A or
2. A has an element A\[j\] such that max \< A\[j\]

Max is initialized to and assigned to elements of A - so (1) is impossible.

After the j-th iteration of the for loop (lines 4 - 6), max \>= A\[j\]. From lines 5,6 **max only increases**. Therefore upon termination, max \>= A\[j\] which contradicts (2).

**End Of Slides**

This algorithm (first slide) finds the max element in the array. This is a proof by contradiction. Isn't this algorithm already proved when it gets to **max \>= A\[j\] in the last line of the second slide**. Is **which contradicts (2)** even necessary? Because in the second slide you showed max is in the array, and then **you met the condition of a maxium m: an element m of A such that m \>= A\[j\] for all 1 \<= j \<= A.length.**

**This seems to be two proofs in one**. And since it seems to me that the direct proof happens first, then the proof by contradiction is redundant and therefore not necessary. **Am i missing something here? Is this only a proof by contradiction? Or is it a direct proof instead?**

**The image below is just the slides 1 and 2 that I transcribed above. From York University.**

# Answer
You seem to think the structure of the proof is:

1. suppose the algorithm is incorrect;
2. prove that the algorithm is, in fact, correct;
3. this contradicts 1., so the algorithm is correct.

That's almost, but not quite true. Step 2 doesn't prove that the returned value $\mathrm{max}$ is bigger than every element of the array, which is what would be required to prove that the algorithm is correct. It just proves that $\mathrm{max}$ is bigger than the specific array value that was supposed to be a counterexample in step 1.

But, as Yuval has pointed out, the proof is much easier if you forget about contradiction completely and prove that $\mathrm{max}$ is in the array (identical to the given proof) and then show that $\mathrm{max}$ is at least as big as every array element (identical to the proof except "for all $j$" instead of just for one supposed counterexample.
> 4 votes

# Answer
It's a proof by contradiction that could easily be rewritten as a direct proof.

To rephrase it as a direct proof, we divide it into two claims:

1. $max$ is an element of $A$.
2. $max \geq A\[j\]$ for all $j$.

We can conclude that $max = \max(A)$.
> 3 votes

---
Tags: algorithms, correctness-proof, check-my-answer
---


# Question
Title: Sorting an "almost sorted" array in sub linear time
I am given an "almost sorted" array with the condition that each element is no more than $k$ places away from its position in the sorted array. I need to show that it is impossible to sort this array in sublinear time asymptotically.

My proof is to suppose a sorted array of length $n$. Now assume that every second element is swapped with the element on its left. The new array is almost sorted. To sort it would require a minimum of $n/2$ swaps - asymptotically linear amount of operations. Therefore, no sublinear sorting algorithm exists.

Is this proof correct?

# Answer
It is correct, but you should be careful to stipulate that the swaps are performed in a non overlapping fashion; if the swaps overlap then one element can be carried across the array breaking the guarantee.
> 2 votes

# Answer
This is correct, but more complicated than it needs to be.

Consider an array of $n$ elements which is sorted except for that *one* (unknown) pair of elements is swapped.

Since the sorting algorithm does not know in *which* pair of elements is swapped, any individual element of the array may be in the wrong place. So, we have to make $O(n)$ comparisons to check if each element needs to be moved or not.

Therefore, the complete algorithm cannot be faster than $O(n)$.

The condition that "each element is no more than $k$ places away from its position" is irrelevant, though it might mislead you to waste time looking for a faster algorithm which depends on that condition!
> 0 votes

---
Tags: algorithms, sorting, check-my-answer
---


title: Job scheduling approximation

text:
# Question
Title: Job scheduling approximation
In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf

Lemma 5 is given as:

> The approximation factor of the modified greedy \[scheduling\] algorithm is 4/3.

And gives the example:

> Note that 4/3 is essentially tight. Consider an instance with $m$ machines, $n = 2m+ 1$ jobs, $2m$ jobs of length $m + 1, m + 2, · · · , 2m − 1$ and one job of length $m$.

does the above example have an error as a proof of lemma 5?

I have been thinking about it over a day.

# Answer
> 1 votes
The instance in the example is "almost" the right one, however you are right that, as given, it does not prove tightness. The instance is missing **two more jobs of size $m$**.

After we include these two jobs, we have 2 jobs of each size from $2m-1$ to $m+1$ and 3 jobs of size $m$ (for $n=2m+1$ jobs in total, as stated).

Under the modified greedy algorithm, the maximum load will be $4m-1$. However, one can instead schedule a job of size $2m-i$ with a job of size $m+i$ for each $i=1,2,..., \lfloor m/2 \rfloor$, and the remaining 3 jobs of size $m$ separately on the same machine. The maximum load will then be $3m$.

---
Tags: algorithms, approximation, arrays, subset-sum
---


# Question
Title: Simulating a probability of 1 of 2^N with less than N random bits
Say I need to simulate the following discrete distribution:

$$ P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} $$

The most obvious way is to draw $N$ random bits and check if all of them equals to $0$ (or $1$). However, information theory says

$$ \begin{align} S & = - \sum\_{i} P\_i \log{P\_i} \\ & = - \frac{1}{2^N} \log{\frac{1}{2^N}} - \left(1 - \frac{1}{2^N}\right) \log{\left(1 - \frac{1}{2^N}\right)} \\ & = \frac{1}{2^N} \log{2^N} + \left(1 - \frac{1}{2^N}\right) \log{\frac{2^N}{2^N - 1}} \\ & \rightarrow 0 \end{align} $$

So the minimum number of random bits required actually *decreases* as $N$ goes large. How is this possible?

Please assume that we are running on a computer where bits is your only source of randomness, so you can't just tose a biased coin.

# Answer
Wow, great question! Let me try to explain the resolution. It'll take three distinct steps.

The first thing to note is that the entropy is focused more on the *average* number of bits needed per draw, not the maximum number of bits needed.

With your sampling procedure, the maximum number of random bits needed per draw is $N$ bits, but the average number of bits needed is 2 bits (the average of a geometric distribution with $p=1/2$) -- this is because there is a $1/2$ probability that you only need 1 bit (if the first bit turns out to be 1), a $1/4$ probability that you only need 2 bits (if the first two bits turn out to be 01), a $1/8$ probability that you only need 3 bits (if the first three bits turn out to be 001), and so on.

The second thing to note is that the entropy doesn't really capture the average number of bits needed for a single draw. Instead, the entropy captures the *amortized* number of bits needed to sample $m$ i.i.d. draws from this distribution. Suppose we need $f(m)$ bits to sample $m$ draws; then the entropy is the limit of $f(m)/m$ as $m \to \infty$.

The third thing to note is that, with this distribution, you can sample $m$ i.i.d. draws with fewer bits than needed to repeatedly sample one draw. Suppose you naively decided to draw one sample (takes 2 random bits on average), then draw another sample (using 2 more random bits on average), and so on, until you've repeated this $m$ times. That would require about $2m$ random bits on average.

But it turns out there's a way to sample from $m$ draws using fewer than $2m$ bits. It's hard to believe, but it's true!

Let me give you the intuition. Suppose you wrote down the result of sampling $m$ draws, where $m$ is really large. Then the result could be specified as a $m$-bit string. This $m$-bit string will be mostly 0's, with a few 1's in it: in particular, on average it will have about $m/2^N$ 1's (could be more or less than that, but if $m$ is sufficiently large, usually the number will be close to that). The length of the gaps between the 1's are random, but will typically be somewhere vaguely in the vicinity of $2^N$ (could easily be half that or twice that or even more, but of that order of magnitude). Of course, instead of writing down the entire $m$-bit string, we could write it down more succinctly by writing down a list of the lengths of the gaps -- that carries all the same information, in a more compressed format. How much more succinct? Well, we'll usually need about $N$ bits to represent the length of each gap; and there will be about $m/2^N$ gaps; so we'll need in total about $mN/2^N$ bits (could be a bit more, could be a bit less, but if $m$ is sufficiently large, it'll usually be close to that). That's a lot shorter than a $m$-bit string.

And if there's a way to write down the string this succinctly, perhaps it won't be too surprising if that means there's a way to generate the string with a number of random bits comparable to the length of the string. In particular, you randomly generate the length of each gap; this is sampling from a geometric distribution with $p=1/2^N$, and that can be done with roughly $\sim N$ random bits on average (not $2^N$). You'll need about $m/2^N$ i.i.d. draws from this geometric distribution, so you'll need in total roughly $\sim Nm/2^N$ random bits. (It could be a small constant factor larger, but not too much larger.) And, notice is that this is much smaller than $2m$ bits.

So, we can sample $m$ i.i.d. draws from your distribution, using just $f(m) \sim Nm/2^N$ random bits (roughly). Recall that the entropy is $\lim\_{m \to \infty} f(m)/m$. So this means that you should expect the entropy to be (roughly) $N/2^N$. That's off by a little bit, because the above calculation was sketchy and crude -- but hopefully it gives you some intuition for why the entropy is what it is, and why everything is consistent and reasonable.
> 28 votes

# Answer
You can think this backwards: consider the problem of binary encoding instead of generation. Suppose that you have a source that emits symbols $X\in \\{A,B\\}$ with $p(A)=2^{-N}$, $p(B)=1-2^{-N}$. For example, if $N=3$, we get $H(X)\approx 0.54356$. So (Shannon tells us) there is an uniquely decodable binary encoding $X \to Y$, where $Y \in \\{0,1\\}$ (data bits), such that we need, on average, about $0.54356$ data bits for each original symbol $X$.

(In case you are wondering how such encoding can exists, given that we have only two source symbols, and it seems that we cannot do better that the trivial encoding , $A\to 0$, $B\to 1$ , with one bit per symbol, you need to understand that to approximate the Shannon bound we need to take "extensions" of the source, that is, to code sequences of inputs as a whole. See in particular arithmetic encoding).

Once the above is clear, if we assume we have an invertible mapping $X^n \to Y^n$ , and noticing that, in the Shannon limit $Y^n$ must have maximum entropy (1 bit of information per bit of data), i.e., $Y^n$ has the statistics of a fair coin, then we have a generation scheme at hand: draw $n$ random bits (here $n$ has no relation with $N$) with a fair coin, interpret it as the output $Y^n$ of the encoder, and decode $X^n$ from it. In this way, $X^n$ will have the desired probability distribution, and we need (in average) $H(X)\<1$ coins to generate each value of $X$.
> 2 votes

---
Tags: algorithms, information-theory, randomness, pseudo-random-generators, entropy
---


# Question
Title: How do you marginalize in graphical model elimination?
I'm reading Michael I. Jordan's book on probabilistic graphical models, and I don't understand the elimination algorithm presented in chapter 3. To narrow the question down, consider page 6. In equation (3.10), we see that $$m\_5(x\_2,x\_3) = \sum\_{x\_5}p(x\_5|x\_3)p(\bar{x}\_6|x\_2,x\_5)$$

where the $x\_i$ are random variables and $\bar{x}\_i$ indicates a fixed/realized value of $x\_i$.

Given that all $x\_i$ are discrete random variables (as is the case in chapter 3), both $p(x\_5|x\_3)$ and $p(\bar{x}\_6|x\_2,x\_5)$ are represented by two-dimensional matrices. And since $m\_5$ is a function of as-yet unrealized variables $x\_2$ and $x\_3$, it is also a two-dimensional matrix.

How then do we perform the multiplication and the summation above?

# Answer
> 1 votes
I'm realizing now that it's just regular matrix multiplication.

For the case above, let $p(x\_5|x\_3)$ and $p(\bar{x\_6}|x\_2,x\_5)$ be represented by $r\\!\times\\!s$ and $s\\!\times\\! t$ matrices, respectively, where $x\_5$ can take on $s$ different values. Then, for each element $m\_{ij}$ of $m\_5$, we have that

$$m\_{ij}=\sum\_{k=1}^s p\_{ik}(x\_5|x\_3)p\_{kj}(\bar{x\_6}|x\_2,x\_5)$$

where $1\leq i \leq r$ and $1 \leq j \leq t$.

This is matrix multiplication. Also, intuitively, the dimensions will always work out, since each factor in the product will always be a function of the variable we're summing over.

I think the notation is what was tripping me up. I usually don't see matrix multiplication written explicitly as a sum of products.

---
Tags: probability-theory, graphical-models
---


# Question
Title: Approximation ratio of greedy algorithm for makespan
In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf

Lemma 5 is given as:

The approximation factor of the modified greedy \[scheduling\] algorithm is 4/3.

And gives the example:

Note that 4/3 is essentially tight. Consider an instance with m machines, n=2m+1 jobs, 2m jobs of length m+1,m+2,⋅⋅⋅,2m−1 and one job of length m.

now how can number of integers in the range m+1,m+2,....,2\*m-1,be 2\*m ?

# Answer
> 2 votes
The lecture notes might be misquoting the example. Here is a correct version, copied from lecture notes of Ola Svensson:

> The 4/3 bound is tight, an infinite family of instances showing this is given below.
>
> **Instance:** we are given $m$ machines, and $2m+1$ jobs. There are three jobs with processing time $m$, and $2$ jobs with processing times $m+ 1,m+ 2,\ldots,2m−1$ each. In case of LPT, all but one of the machines get two jobs with a total processing time of $3m−1$, and a single machine gets three jobs with a total of $4m−1$ processing time. Thus, the makespan is $4m−1$. OPT schedules the three $m$ jobs on a single machine, and the remaining jobs on the remaining $m−1$ machines, such that each of those machines get jobs with a total processing time of $3m$, thus the makespan of OPT is $3m$. As $m$ grows towards infinity the approximation ratio approaches $4/3$.

In the quote, LPT is the greedy algorithm. The approximation ratio for given $m$ is $\frac{4m-1}{3m} = \frac43 - \frac1m$, which tends to $\frac 43$ as $m\to\infty$.

---
Tags: algorithms, approximation, scheduling
---


# Question
Title: What are the other language models of computation similar to lambda calculus?
I hope this question makes sense, but I was wondering if there are other models of computation similar to lambda calculus that you can use to build up axiomatic mathematical and logical fundamentals like numbers, operators, arithmetic functions and such?

# Answer
Yes, there are many models of computation, and of those many are extensions or modifications of the $\lambda$-calculus. You may wish to learn about partial combinatory algebras, which are very general models of computation, of which the $\lambda$-calculus is an example. Every partial combinatory algebra has a $\lambda$-like notation for defining functions. They encompass examples such as: $\lambda$-calculus, Turing machines, Turing machines with oracles, topological models of computation, PCF, etc.

Many models of computation can be seen as extensions or modifications of the $\lambda$-calculus. Let us consider the simply typed $\lambda$-calculus augmented with various features:

1. System T is $\lambda$-calculus with natural numbers and primitive recursion. It is *not* Turing complete.
2. The aforementioned PCF is $\lambda$-calculus extended with natural numbers and general recursion. It is Turing complete.
3. There are many extensions of PCF, for instance PCF++ can perform parallel computations, PCF+`catch` can throw and catch exceptiosn, PCF+`quote` can disasemble code into source code, etc. These are all *different* computation models based on the $\lambda$-calculus.
4. In another direction, we can extend the $\lambda$-calculus with more powerful types, for instance System F is a $\lambda$-calculus with polymorphic types. It is quite powerful but not Turing complete.

All of this is just scratching a rich theory of models of computation and functional programming languages (which is what extensions of $\lambda$-calculus are, more or less). If you are interested in the topic, you can start by reading some books on the principles of programming langauges (for practical aspects), or some books on realizability theory (for theoretical aspects).
> 5 votes

# Answer
Historically, Church, Kleene, and perhaps others argued for recursive functions to capture mathematical reasoning. Godel instead posed mathematical reasoning as syntax in logical symbols. There is a story, as told by Wadler, (here if the link still works) that Church showed Godel their different notion were equivalent, causing Godel to remark that therefore neither model expresses mathematical reasoning accurately. Turing added a further formulation that any "Turing complete" machine could reproduce both Godel's model and Church's model. ...so... insofas $\lambda$-calculus is just a syntax for evaluating functions there isn't really any strength here that couldn't for example be achieved by strings in a Turing Machine or strings in PHP. As long as a computational model is Turing complete at least there should be an equivalent way to do all computations. This is roughly the statement of today's "Turing-Church Thesis". Belief in whether this capture mathematical sophistication is a personal choice, but it says that you really can't invent a Turing complete programming model that can't do math. So in that sense the answer to your question is *almost every* programming language.

Even so, some languages that leverage mathematical axioms (Idris, Agda), theorem proving etc. actually try to restrict you to "total functions" meaning all inputs have an output in finite time (no infinite recursions). Those are actually less powerful than say C or PHP in that they are not Turing complete. But as Edwin Brady is happy to remind people, it is still likely that most interested programs such as "Pac-man" can be written in total languages.

I think the spirit of you question is to spark a list of programming abstractions related to mathematical reasoning. To that I would say beyond the syntax of $\lambda$-calculus the following are essential for making any mathematical reasoning readable and thereby useable.

* A good way to distinguish values/varaibles, from functions, from relations. This could be a set theory or a type theory. In vogue today are dependent types (or path-dependent as in Scala if thats what you can get). Mathematics however is still largely in the set groove so there is a need to translate. But however the model it needs to be clear that there are elements to input to a function, and that the elements together can be collected into different clumps (sets or types) and that we can impose relationships between the elements in clumps (equivalence, partial orders etc.)
* Good type inference. Math doesn't say what $x$ or $2$ is everytime it uses it in an equation, it would be too hard to get going or to read. The programming language has to be able to figure that out on its own from context. To me type inference means that with very little writing the reader and the programming language can tell whether we intend a value/varaible/function/ or relation, and place it if need be within a constrained context, such as a set or type.
* Implicit context -- similar to type inference, we need not only the types but the functions to be self-evident from context even if their exact syntax can be found elsewhere with different meaning. This is more than type checking. E.g. $x\*y\*z$ needs to have the type inference tell you what $\*$ means, but it also needs to be clear that this could be treated as $(x\*y)\*z$ or as $x\*(y\*z)$ which is an axiom on $\*$ you wouldn't bother to expressly mention but would be critical to some type-checking. So implicit context to me is the addition of theory given by the axioms. It is ok (and necessary) that this theory be constructive, i.e. a language is only required to invoke theorems it has already proved. But it should largely on its own look up what is already known, perhaps with hints (often called "tactics").

Given all that, its quite fun to explore, and many languages now can handle this. But I would say still so far *none* do such a great job. So far most systems are reasonably good at axioms in 1st order logic. E.g. equations that have to hold such as `Length(List1 cat List 2)=Lenght(List1) + Length(List2)`. That really is far short of high-level reasoning about numbers.

A programming languages still can't reason well about relations, e.g. quotients, homotopies, and equivalences. As a simple exercise consider how you would write a program that produced the field $\mathbb{Z}/p$ for a prime $p$. How would you prove non-zero elements have inverses? Its a simple mathematical expression to state $(\forall x)(x\neq 0\Rightarrow (\exists y)(xy=1))$. But somewhere down the line you have to hide a proof that $p$ is prime (here I mean $p$ is a variable to your dependently typed $\mathbb{Z}/p$). After AKS that can be done but not at all trivially in the type system. Without this you wont get to build say linear algebra over finite fields or prove some RSA system is correct etc.

As a larger point, most languages hope to express objects with equivalent types as normal forms, and then compare normal forms. This can be incredibly expensive computationally. And if your language is Turing complete it can actually be impossible.
> 3 votes

---
Tags: computability, logic, lambda-calculus, mathematical-foundations
---


# Question
Title: Regularity of a language contains more 1's than 0's
The language of all bitstrings with more 1s than 0s, i.e.,

$ A = \\{x: 2\Sigma\_{i}^{|x|} x\_{i} \> |x|\\}$ is regular.

I know I should apply Pumping Lemma and the proof as well, what I cannot understand is' the meaning of question itself. To be more precise, my question is' how the formal and informal sections of the question are the same?

# Answer
Treat the characters of the string as integers and add them up. The number you get is the number of ones in the string. If that number is more than half the length of the string, then there are more ones than zeros.

In my opinion, that's not a good way to specify the language. It's clever and correct but, honestly, if somebody has to ask a Stack Exchange question about the way you chose to write "More ones than zeros", then you made it way too hard to understand.
> 0 votes

# Answer
the notation $ L = \\{w: 2\*\Sigma\_{i}^{|w|} w\_{i} \> |w|\\} $

is the same as: $ L = \\{w: 2\*\Sigma\_{w\_i=1} w\_{i} \> |w|\\} $

it means all the words $w$ s.t the number of $1$'s they contain is essentially greater than half of $|w|$ (the length of the word).

so if $x\_0, x\_1$ denote the number of $0$'s and $1$'s respectively, it is required that $2x\_1 \> |w|$

in other words, more than half the bits are $1$, so essentially the word has more $1's$ than $0$'s
> 0 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Shortening the number of reductions to prove NP-Completeness
This question is based on the slides from this pdf:

* Slide **54**, they define the Subset Sum Problem.
* Slide **65**, they define the Partition problem.
* Slide **74**, they talk about the Job Scheduling problem.

My question is, is it possible to cut the middle man of the partition problem and reduce Subset Sum to Job Scheduling directly?

---

To prove scheduling is NP, we can use what is already stated since it's not related to partition.

I'm not sure how to combine the reduction from both onto one though.

# Answer
Yes, that's possible.

The reduction from Subset Sum to Partition is a mapping $f$ from Subset-Sum-instances to Partition-instances. The reduction from Partition to Job Scheduling is a mapping $g$ from Partition-instances to Job-Scheduling-instances. So, the function $g \circ f$ is a mapping from Subset-Sum-instances to Partition instances.

This gives you a direct reduction in one step; the reduction is given by the function $g \circ f$. If you work through the details of the construction of $f$ and $g$, you should be able to figure out what $g \circ f$ is doing. If you wanted, you could write down the definition of the function $g \circ f$ without telling anyone that it came from composing $f$ and $g$. Whether that would be useful in any way is a different question...
> 1 votes

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


# Question
Title: shortest form $s$ to $t$ stopping at $u$
> Suppose you want to go from vertex $s$ to vertex $t$ in an unweighted graph $(V, E)$, but you would like to stop by vextex $u$ if it is possible to do so without increasing the length of your path by more than a factor $\alpha$. Find an efficient algorithm that would determine an optimal $s-t$ path given your preference to stopping at $u$ along the way if doing so is not prohibited costly.

Here is my try :

First perform a BFS from $s$. When you get at $t$ you know what is the shortest past in $G$ from $s$ to $t$. We denote the size of this shortest path by $P$. Now we perform an other BFS from $s$, when we get at $u$ we know what is the shortest path $M$ from $s$ to $u$. Once again we perform a BFS from $u$ and when we get at $t$ we know what is the shortest path $K$ form $u$ to $t$. If $\mid M \mid+\mid K \mid \leq \alpha P$ then the optimal path $(M,K)$ is a solution. So we are performing $3$ times a BFS in $G$, thus the overall complexity is $O(X + Y)$ where $X$ is the number of edges and $Y$ the number of vertex.

Is it possible to do better? Is what I said correct?

# Answer
> 2 votes
What you said is true.

Using your notations:

$P$ : path from $s$ to $t$

$M$ : path from $s$ to $u$

$K$ : path from $u$ to $t$

Notice that $P,M,K$ are all shortest paths from their respective sources to their targets.

Following the logic above:

$M \cup K$ is the shortest path from $s$ to $u$ to $t$

hence if $|M \cup K|$ is a good enough result for you - accept it. If it's not, i.e $|M \cup K| \> \alpha|P|$, then essentially no shorter path exists from $s$ to $t$ using $u$.

(you can try proving $|M \cup K| \geq |P|$, may help your intuition!

---
Tags: algorithms, complexity-theory, graphs, optimization
---


# Question
Title: Minimum difference between two subsets of an array of integers
## The Problem

Suppose we have an array A\[1...n\] of integers, with values ranging from 0 to K (so 0\<=A\[i\]\<=K for each i). We need to describe an algorithm to find an (X,Y) partition from the set {1,2,...,n} such that |Sx-Sy| is minimum, where Sx and Sy are the sums of the elements in X and Y. i.e., if A=\[1,3,1,1\], then X={1,3,4} and Y={2} and the solution is optimal with Sx=3, Sy=3, |Sx-Sy|=0.

## My Solution (In pseudocode)

```
For i=0 to n
    if A[i]==K //If this element is the highest element in the array, put it in Sy
        Sy.add(A[i])
Else if A[i]=/=0 //We don't care about zeroes, the rest goes in Sx
    Sx.add(A[i])
min = |Sx-Sy| //Calculate our min as it is
DO
    go=false
    //Move the smallest element from the biggest group to the other one
    if Sx>Sy
        SyTemp = Sy + min(Sx)
        SxTemp = Sx - min(Sx)
    else if Sy>Sx
        SxTemp = Sx + min(Sy)
        SyTemp = Sy - min(Sy)
    //if this improves on our min, save it and check for another iteration
    if |SxTemp-SyTemp|<min
        Sx=SxTemp
        Sy=SyTemp
        min = |Sx-Sy|
        go=true
    else
        Return Sx,Sy //if the new sets are worse than the ones before, return the old ones
While(go)

```

## My question

Apparently, this problem is NP complete (At least that is what my professor told me), and my question comes from the way he scored my solution. I got 3 points out of 9 because a dynamic programming solution is what was requested - while this is a greedy approach - and my solution has edge cases in which it won't work.

the example he gave me to prove that these edge cases exist was \[1,2,5,5\] and he said that in this case the algorithm would return {1,2,5},{5} instead of {1,5},{2,5}. Now, to me it seems like my solution would actually return what he wants, and I can't really think of an example this algorithm couldn't deal with, so I'm here to ask the community if you see any errors in my solution, if you think my professor is right in saying that his example wouldn't be solved optimally (or that there are edge cases in which this approach won't work), and if you think this will perform better than O(K(n^2)), where K is the sum of all values of the array (which apparently is the time complexity of his DP solution).

# Answer
> 3 votes
My algorithm got proven wrong by Ricky Demer in a comment to the OP, with the example \[2,2,3,3\], for which we have a suboptimal output ({2,2} and {3,3} instead of {2,3} and {2,3}, for those wondering). Altough this flaw could be fixed in my code, it would then perform suboptimally in the example my professore had given me (And that I wrote in the OP).

A good greedy version of the algorithm is given on Wikipedia and is as follows:

```
def find_partition(int_list):
"returns: An attempt at a partition of `int_list` into two sets of equal sum"
A = set()
B = set()
for n in sorted(int_list, reverse=True):
    if sum(A) < sum(B):
       A.add(n)
    else:
       B.add(n)
return (A, B)

```

This approach gives a 7⁄6-approximation of the optimal solution, thus the only viable technique to use in case you need an optimal algorithm is dynamic programming. An implementation can be found, again, on Wikipedia and will run in pseudo-polynomial time.

# Answer
> -2 votes
This will help to get the subset

```
numbers=[5,6,1,11]
numbers.sort(reverse = True)
total=sum(numbers)/2
S1=[]
S2=[]
for i in numbers:
    if(i+sum(S1)-total)<0:
        S1.append(i)
    else:
        S2.append(i)
print ('S1' ,S1)
print ('S2',S2)

```

Source :https://www.youtube.com/watch?v=XafGZHCxdc0

---
Tags: algorithms, dynamic-programming, greedy-algorithms
---


title: Basic Set Theory problem

text:
# Question
Title: Basic Set Theory problem
So i'm relatively new to computer science and have been learning set theory and am stumped on a question in it.

The question specifies that we're only looking at subsets of universe U = {0,...,n-1}. For a set S ⊆ U, the characteristic vector denoted by Xs is an n-bit string where j is 1 if and only if j ∈ S. Example, n = 4, S = {1, 3} Xs = 1010.

it is asking what is XØ and XU. I think I am completely overthinking this but I can't figure out what XØ and XU are referring to.

# Answer
> 5 votes
Characteristic vector is a string representation of a set in this case. For a set $S$, the characteristic vector is denoted by $X\_S$. $X\_\emptyset$ and $X\_U$ are referring to the characteristic vector of $U$ (Universal set) and $\emptyset$ (Empty set) respectively. In your example, $$\text{If }n = 4 \text{ and } S = \\{1, 3\\} \text{, then } X\_s = 1010.$$ We simply need to replace $S$ with a set $\\{0, 1, 2, \dots n-1\\}$ to find $X\_U$ and with $\\{\\} = \emptyset$ to find $X\_\emptyset$. I think you can leave $n$ as a variable unless it is fixed to some value.

---
Tags: sets, computer-algebra
---


# Question
Title: what is the difference between Operating system and Window Systems?
Quoting from Tannenbaum\_Operating\_Systems\_Design :

> On top of the operating system is the rest of the system software. Here we find the command interpreter (shell), **window systems**, compilers, editors, and similar application-independent programs. It is important to realize that these programs are definitely not part of the operating system

I am not getting the difference between these two keywords ,isn't the Windows an Operating system so what's the meaning of this Window Systems which is not the part of Operating System. When we say that windows is an operating system then how can we make a distinction between windows systems and an Operating system ?

# Answer
> 1 votes
I think you misunderstand the window systems. It is software to manage different parts of the display screen, not the Windows OS. In Microsoft's Windows OS, the window system is Desktop Window Manager.

---
Tags: operating-systems
---


# Question
Title: The time complexity of finding the kth smallest number using buckets
I've implemented kth smallest number using buckets representing the `current` nibble value of each element in the array where `current` is a value starting possibly at 64 (for 64 bits integers at most) and decrements each iteration by 4 (nibble size).

I was wondering what is the time complexity (worst) of this implementation. I think it's `O(n^log64/4)` which is `O(n^16)`, is that correct?

```
function nthSmallest(array, k, sizeOfInt) {
    let buckets = [
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        []
    ];
    // put numbers in buckets - O(n)
    for (let i = 0; i < array.length; i++) {
        const high = (array[i] >> sizeOfInt - 4) & 0xF; // 4 = nibble size
        buckets[high].push(array[i]);
    }
    let numbers = [];
    for (let i = 0; i < buckets.length && numbers.length < k; i++) {
        if (numbers.length === k - 1 && buckets[i].length === 1) {
            return buckets[i][0];
        }
        for (let j = 0; j < buckets[i].length; j++) {
            numbers.push(buckets[i][j]);
        }
    }
    return nthSmallest(numbers, k, sizeOfInt - 4);
}

```

# Answer
> 1 votes
Your algorithm is a variant of the radix sort.

Consider $k=n$ and the greatest two numbers differ by only the least 4 significant bits, then the two greatest numbers will be always in the last buckets in each iteration except the last. This means you have to iterate for `sizeOfInt`, `sizeOfInt - 4`, ... until `4`, so the overall complexity is $O(nw)$ where $w$ is `sizeOfInt`.

---
Tags: algorithms, time-complexity, arrays
---


# Question
Title: Sphere packing inequality for error-correcting codes
i am wondering if the following inequality is correct:

if a code allows repairing of no more than k errors (inclusive, included) and m is the number of information bits and r the check bits, then $$∑^k\_{i=1}\binom{m+r}{i}+1≤2^r$$

holds true?

please if you can explain so i can understand how you choose answer you give.

the only inequality i find in books that look similar is about "perfect code" with the inequality given is: $2^n = 2^k\sum\_{i=0}^k\binom n i$. but i not see how this code is relevant. i try to do research in other books or internet and no answer sadly. please help me understand if given inequality is true or not based on information given.

thank you much.

# Answer
> 3 votes
For a codeword $x$, let $B\_k(x)$, the ball of radius $k$ around $x$, consist of all words at distance at most $k$ from $x$. Notice that $$|B\_k(x)| = \sum\_{i=0}^k \binom{m+r}{i}. $$ If the code supports correcting up to $k$ errors, then the sets $\\{ B\_k(x) : x \in C \\}$ must be disjoint. The code contains $2^m$ many different codewords, hence we get $$ 2^m \sum\_{i=0}^k \binom{m+r}{i} \leq 2^{m+r}, $$ which is the same as your inequality. Here $m+r$ is the length of each codeword, and $2^{m+r}$ is the number of possible vectors.

If your code is $q$-ary rather than binary, then the same calculation shows that $$ \sum\_{i=0}^k (q-1)^i \binom{m+r}{i} \leq q^r. $$

---
Tags: information-theory, coding-theory, error-correcting-codes
---


# Question
Title: Variable Capturing With Repetition of Variable Name
I am very confused as to which variables are captured by which λ in the example below:

```
(λa.λb.(λa.a)aba)(ab)

```

I am new to lambda calculus and the repetition of variables makes this example hard for me to understand and reduce. Any help would be appreciated!

# Answer
If you make the construction tree of the expression, a variable $x$ of a leaf refers to that $\lambda x$ which is closest to $x$ in the path from $x$ to the root.

Another way to see it is with the use of scoping rules. The scope of each $\lambda$ is the body of the $\lambda$.

So, the scope of the inner-most $\lambda a$ is only $a$. This means that any occurrence of $a$ outside that parenthesis refers to a different variable than the $a$ inside the parenthesis (point 1).

The scope of the $\lambda b$ is $(λa.a)aba$, so similarly any $b$ outside this expression refers to a different variable (that just happens to have the same name).

The scope of the outermost $\lambda a$ is $\lambda b.(\lambda a.a)aba$. Here things are a bit more complex, because there's another $\lambda a$ inside. But according to point (1) the $a$ in $\lambda a.a$ is different than the $a$'s in the rest of the body. So, only the $a$'s in $aba$ refer to the outermost $\lambda a$.

Note that there are no lambda's to bind the $a$ and $b$ in subexpression $(ab)$ (on the right of the expression). Therefore, the $a$ and $b$ in $(ab)$ occur free.
> 2 votes

---
Tags: lambda-calculus
---


title: Turing machine accepts any word

text:
# Question
Title: Turing machine accepts any word
> Let M be a Turing-machine with tape alphabet = {0, 1} that does not move beyond the first 64 cells of its tape. Is the problem "Does M accept any word?" decidable?

1. I would say it does not accept any word because we can have words longer than 64 characters.
2. I would say it does because if it accepts any word, we don't care about the length. It always goes into accepting state.

Can someone please explain this to me?

# Answer
Let $P = \\{ w \in \\{ 0,1 \\} \mid |w| \le 64 \land w \in L(M) \\}$. Since $P$ contains only words over an alphabet (i.e., a *finite* set) and all words in $P$ have bounded length, $P$ is finite. Moreover, any word $w \in \\{0,1\\}^\ast$ with length $|w| \> 64$ is in $L(M)$ if and only if there is a prefix of $w$ which is in $P$. Thus, to decide $L(M)$, we only need to check whether the input has a prefix out of finitely many possibilities (i.e., those in $P$).

Hence, $L(M)$ is not only decidable, it is decidable *in constant time*.

Note this construction does not require any knowledge of $M$ whatsoever (in particular, there is no need to simulate $M$). We only need to show the *existence* of a TM which decides $L(M)$, not actually *construct* one.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Decidability problem solved by an alogrithm step by step difference between Decision and decidable problem
How Decision procedure and Decidable problem are different from each other? Both are having solutions in yes and no form. Is any else solution for both?

# Answer
A decision problem is a problem of the form "Is my input in this set?", with a yes/no answer. A decidable problem is a decision problem that can be solved by a Turing machine.
> 1 votes

---
Tags: automata
---


title: Constant time range sum query

text:
# Question
Title: Constant time range sum query
I need to come up with a data structure that supports the following interface:

* new(time\_stamp x, value v): insert a new data v for time stamp x
* update(time\_stamp x, value v): update the data for time stamp x to v
* delete(time\_stamp x): delete the data for time stamp x
* query(time\_stamp x): returns sum of all data whose time stamp is less than or equal to x

The data structure needs to support out of sequence data. I need the query operation to run in O(1) time. While there is no restriction for other provided interfaces, I don't want to end up with O(n) time complexity for any of them.

An AVL tree seems a good candidate, however I'm not aware of any technique (maybe amortized cost analysis) to reduce the O(log n) query complexity for AVL tree to O(1).

I appreciate any suggestion or direction toward implementing such a data structure.

# Answer
If the timestamps can take $T$ different values, then it is simple to implement the new, update, and delete operations in time $\Theta(T)$ and the query in time $O(1)$, by maintaining two arrays $val\[ \]$ and $q\[\]$ of size $T$. The array $q\[\]$ is initially filled with zero values.

* new(x, v): set $val\[x\] = v$ and increment each $q\[y\]$ with $y\ge x$ by $v$;
* update(x, v): let $v' = val\[x\]$; increment each $q\[y\]$ with $y \ge x$ by $v-v'$, then set $val\[x\]=v$;
* delete(x, v): let $v' = val\[x\]$; decrement each $q\[y\]$ with $y \ge x$ by $v'$;
* query(x): return $q\[x\]$.

Note that $n$ (number of data items, that is, the number of total calls to new) is unrelated to $T$ (range of the timestamps). Whenever $T=o(n)$, the above implementation satisfies your requirements. For example, if a timestamp is a day of the year, $T$ will be a constant, even though $n$ can be arbitrarily large (because you can have arbitrarily many new and deletes).

If, on the other hand, $T$ can be larger than $n$, then as D.W. noted in his comment your requirements may be too strict.
> 1 votes

---
Tags: data-structures, time-series-analysis
---


title: PRAM with no bit operations and P vs NC

text:
# Question
Title: PRAM with no bit operations and P vs NC
I was reading up on something called the PRAM model without bit operations. What exactly does it mean that this PRAM model cannot do bit operations? I can't find a straightforward definition anywhere.
Surely the different processors will still be able to do all sorts of stuff with bits. The reason why I am asking is that the max-flow problem (which is in P cannot be solved in this model using a polynomial number of processors. So in fact it is a non-trivial implication of the conjecture that $P \neq NC$. So it is further "evidence" of the $P \neq NC$ conjecture.

# Answer
Without further information, it's hard to tell exactly. However, to the best of my knowledge, bit operations may be intended as follows. Consider the problem of finding the maximum element in an array of $n$ real numbers. This problem can be solved by an EREW algorithm in $\Omega(\lg n)$; moreover, no CREW algorithm can do any better.

However, this problem can be solved in $O(1)$ time with $n^2$ processors using a common-CRCW algorithm (in this model, when several processors write to the same location, they all write the same value). The key point here is that a CRCW PRAM is capable of performing a boolean AND of $n$ variables in $O(1)$ time with $n$ processors (which allows overcoming the $\Omega(\lg n)$ lower bound). I think that bit operations may refer to this powerful AND capability of a common-CRCW.

Additional information regarding the FAST-MAX algorithm can be found in the first edition of CLRS Introduction to Algorithms, chapter 30 (ALGORITHMS FOR PARALLEL COMPUTERS).
> 2 votes

# Answer
On page 1461 of "Lower Bounds in a Parallel Model without Bit Operations," Mulmuley says:

> It is like the usual PRAM model, the main difference being that it does not provide instructions for any bit operations such as $\land$,$\lor$,or *extract-bit*.

The model is explicitly specified in section 2.1.

The reason I think this result ($\textsf{P}\neq\textsf{NC}$) in this model is interesting is---although this model does not allow bit-operations---it still allows the time to depend on bitlengths. Also, this model is powerful enough to compute the determinant (see paragraph "Arithmetic PRAM model." on page 1469)!
> 1 votes

---
Tags: complexity-theory, computation-models, parallel-computing, max-flow
---


# Question
Title: Term for the use of the same programming language in every tier?
What is the technical term that describes the use of the same programming language in every tier in the architecture of a system? For example, having JavaScript in model, view and controller.

edit #1: MVC was mentioned just to give an example. I read the concept in a book once when I was at the university but can't remember. I've been googling the concept but can't reach it. Thanks again

# Answer
> 0 votes
I it is not widely used terminology, if you use MVC it makes little sense to deploy different languages, because some glue is needed to maintain it (say data sharing between different languages).

The term is monolanguage (monolingual programming) or homogeneous language programming. Similar terms like homogeneous programming are about same hardware used among nodes.
Term monolanguage or homogeneous programming environment is more popular with creating full stack of software based on the same language, which currently is only one.

---
Tags: terminology, programming-languages
---


# Question
Title: What does the intersection symbol (∩) mean when applied to two non-set elements?
I came across a piece of literature in which I saw the intersection symbol (∩) being used on two non-set elements in the definition of an equivalence relation; I have posted it below for reference. The elements in question are meant to represent different files on a computer. What could that intersection symbol mean in this context?

> Let $x\_1$ and $x\_2$ be two files and let v be a given computer virus. We then define the equivalence relation $R\_v$ as follows:
>
> $x\_{1}\\!\mathit{R\_{v}}\\,x\_{2} \\;\\; if \\;\\; x\_{1} \cap x\_{2} \in \left \\{ x\_{1},x\_{2},v \right \\}.$
>
> This is an equivalence relation and any equivalence class of a given element $x$ is defined by $C(x) = \left \\{ y |y\in S \\;\\; and \\;\\; x \mathit{R\_v} y \right \\}$. The class $C(v)$ contains every file infected by $v$. Every class which is a singleton contains an uninfected file.

This text appears in the paper just before the excerpt above and may provide more context:

> Most of self-reproducing codes that exist at the present time are worms and thus a single copy of the malware is present in the system. But it is not the case as far as virus are considered (many copies exist in the system at the same time). In order for our model to be general, we will consider that all the different copies of a malicious codes are in fact a single one, e.g. the viral code. In the very special case of k-ary viruses, the viral code is the disjoint union of k different files.
>
> From a mathematical point of view, it is equivalent to consider the following equivalence relation, which is defined on a set S (the file system).

And even earlier, the text the author describes the $x\_i$ variables as boolean variables:

> In order to define the working context, let is consider an operating system containing $n$ files ($n$ is of arbitrary size). These are all possible files that exist or may exist in the system at a given time. Each of these files are described by a Boolean variable $x\_i$ , $i = 1, 2, . . . , n$. No particular assumptions is made about the status of any of these files (executable or not, data. . .).

Source for the paper: https://link.springer.com/article/10.1007/s11416-007-0044-2

# Answer
> 4 votes
Eh. $\cap$ doesn't mean anything on non-set variables. Looking at the paper, that part of the paper doesn't make any sense to me either. The paper says $x\_1,x\_2$ are Boolean variables, but the notation $x\_1 \cap x\_2$ is not well-defined on two Boolean variables; you can't take the set-intersection of two Boolean variables. If $x\_1,x\_2$ were sets somehow (which the paper says they aren't), then the meaning of $x\_1 \cap x\_2 \in \\{x\_1,x\_2,v\\}$ is that either $x\_1 \subseteq x\_2$ or $x\_2 \subseteq x\_1$ or $x\_1 \cap x\_2 = v$.

So it's anyone's guess what that formula was supposed to represent. If you absolutely must understand the paper, you'll probably have to read the surrounding context to guess what the intention was. Better yet, find a better paper to read, if you can. In any case, the reason you are confused is because what's written is confusing and seems like mathematical gibberish to me. It happens; no one is perfect. Don't assume that just because a paper is published in a journal, that what's written there will necessarily be correct or useful or meaningful.

# Answer
> 3 votes
This is some poorly written textbook. It should distinguish a variable and its realization (i.e. its value). I would rewrite as the following. Let $f\_1$ and $f\_2$ be some file variables. $x\_1$ and $x\_2$ be values of the files. Then $$f\_1 R\_v f\_2 \text{ if } f\_1 = f\_2 \in \\{x\_1, x\_2, v\\}$$

In words (using the original notation), it probably means something like below.

The relation $x\_1 R\_v x\_2$ holds if either of the following is true.

1. $x\_1$ and $x\_2$ contains content of $x\_1$
2. $x\_1$ and $x\_2$ contains content of $x\_2$
3. $x\_1$ and $x\_2$ contains content of the virus $v$

---
Tags: sets
---


# Question
Title: Do all DFA's containing an "accepting path containing a cycle" accept infinite languages?
So I've seen this claim being made on different questions:

Do self-loops in DFA cause infinite languages?

I'd like to find formal proof for this.

I think I should also note that an "accepting path containing a cycle" is probably defined as a path in a graph so that the states in the DFA are nodes in the graph and there must be a cycle and at least one accepting state in that path.

# Answer
> 2 votes
If the DFA contains a path from the start node to an accepting state that contains a cycle, then the DFA is an infinite language. The proof is easy: you can go around the cycle as many times as you like. Depending on how many times you go around the cycle, you get a different word accepted by the DFA; the more times around the cycle, the longer the word (so it has to be different from any word where you went around the cycle a different number of times). There are infinitely many possibilities for how many times you can choose to go around the cycle, so infinitely many words accepted by the DFA.

---
Tags: computability, automata, finite-automata
---


# Question
Title: Tree traversal with conditional summing values from nodes
Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of **value** and a **rank** of node (value as well as rank can be random number). What i want to do is traverse tree and for each node i want to sum values from all descendant nodes **except** descendants with lower rank and all nodes under them (irrespective of rank).

My naive solution is to recursively traverse subtree for each node and stop recursion as soon as i find node with lower rank, summing values on my way back to root of subtree. However this feels to me like suboptimal solution. It is possible to have sums for all nodes settled after one traversal?

Edit: There are no special relationships between nodes and also tree doesnt have any special properties. Tree is not binary tree as each node can have \<0,Integer.MAX\_VALUE\> children.

To more describe my naive solution, in worst case - that is each node has only one descendant (its basically linked list) and ranks are sorted ascending to the root this solution would be O(n^2).

# Answer
This algorithm is simple conceptually, but the implementation is a bit much so I'll try to present it in a couple steps. First, an example.

---

## Linked List Example

Consider the following linked list where rank and value are equivalent: $A = \[1, 3, 5, 6, 4, 2, 0\]$

We will create auxiliary array $S$ where $S\[i\]$ is the sum of the subtree (sub-linked list) rooted at node $i$. This will basically be a suffix sum array for our purposes. This takes $O(n)$ time to create and it would be: $S = \[21, 20, 17, 12, 6, 2, 0\]$.

We will now process the nodes in order, adding them to a stack $T$. We have one rule before adding a node, if the node value on the top of the stack is greater than the node we're adding, then we must pop it from the top of the stack. This will ensure that when we pop a node off the stack, the current node we're at will be the first node lesser than it. Let's say we're popping node $i$ and we're currently at node $j$, then we have the function we're interested in is simply $f(i) = S\[i\] - S\[j\]$. Let's run through this with our example:

```
Let A = [ 1,  3,  5,  6, 4, 2, 0]
Let S = [21, 20, 17, 12, 6, 2, 0] be the suffix sum array of A
Let T be the increasing order stack, initially empty.

1) T = []
2) T = [1]
3) T = [1, 3]
4) T = [1, 3, 5]
5) T = [1, 3, 5, 6]
6) T = [1, 3, 4] and set f(6) = 12 - 6 = 6, set f(5) = 17 - 6 = 11
7) T = [1, 2]    and set f(4) =  6 - 2 = 4, set f(3) = 20 - 2 = 18
8) T = [0]       and set f(2) =  2 - 0 = 2, set f(1) = 21 - 0 = 21
9) T = []        and set f(0) = 0

```

We can take $f$ to be our final answer array where $f = \[21, 18, 11, 6, 4, 2, 0\]$.

---

## Problem with applying this to a Tree

You may notice a problem with applying this to a tree. We are destroying the information of $T$ when we finally get to a leaf node. So to remedy this, we will have to rebuild it in a way as we come back up the recursion stack. For this we will need to keep track of a few more things. First, we will need to know the depth at which a node resides. This is easy to calculate in a single traversal of the tree. Next, we will need to know the depth at which a node was removed from $T$. This is also easy to keep track of during the recursion. So let's move to the next section of the algorithm itself.

---

## The Algorithm Approach

Let's define some things we need. I'll simply add them as pointers on the node itself and assume that our stack $T$ holds a reference to the nodes. For a node $V$ let the node have the following properties:

* `v.rank` \- rank of node $v$. (given)
* `v.value` \- value of node $v$. (given)
* `v.sum` \- the sum of the values of nodes in the subtree rooted at $v$ (precomputed).
* `v.depth` \- the depth of node $v$ where the root is at depth 0. (precomputed)
* `v.removal` \- the depth we are at when we remove node $v$ from $T$. This may be overwritten multiple times throughout the algorithm if $v$ has multiple children.
* `v.f` \- the function we're interested in computing (based on the definition in the question). Initially set `v.f = v.sum`, and we will subtract away subtrees where necessary.

For the sake of dealing with base cases, I will assume w.l.o.g. that leaf nodes will have a dummy node attached to them as a child with value 0 and rank less than that of all nodes in the tree.

So we have our stack $T$, we will also have another stack $R$ which will keep track of the order of the nodes we've removed from $T$. This will be necessary to rebuild $T$ on our way back up from recursion. Assume $T$ and $R$ are global variables.

```
def visit(v, d):
  // Where v is the node we're visiting, and d is the depth we're at.

  // Before recursion
  while top(T).rank > v.rank:
    u = pop(T)
    u.removal = d     // set depth of removal
    u.f = u.f - v.sum // remove sum of subtree rooted at v because it's lesser
    push(R, u)        // push it onto our removal stack R

  if v is not a dummy node:
    push(T, v)
    for each child u of v:
      visit(u, d + 1)

  // Build back up T, we use d - 1 because we're building it back up
  //   so that it is fixed for the level above (when recursion returns)
  while top(T).depth > d - 1:
    u = pop(T)        // we must remove nodes that are depth below our current

  while top(R).depth <= d - 1 and top(R).removal > d - 1:
    u = pop(R)
    push(T, u)

```

---

## Example

Consider this tree (assume rank = value):

Let's work through the first few steps of this example explicitly:

* `d = 0 | v = 2 | T = [2] | R = []` recurse on 4
* `d = 1 | v = 4 | T = [2, 4] | R = []` recurse on 5
* `d = 2 | v = 5 | T = [2, 4, 5] | R = []` recurse on 8
* `d = 3 | v = 8 | T = [2, 4, 5, 8] | R = []` recurse on 7
* `d = 4 | v = 7 | T = [2, 4, 5, 7] | R = [8]` recurse on 0
    + set `8.f = 15 - 7 = 8` and `8.removal = 4`
* `d = 5 | v = 0 | T = [] | R = [8, 7, 5, 4, 2]`
    + set `7.f = 7 - 0 = 7` and `7.removal = 5`
    + set `5.f = 24 - 0 = 24` and `5.removal = 5`
    + set `4.f = 53 - 0 = 53` and `4.removal = 5`
    + set `2.f = 55 - 0 = 55` and `2.removal = 5`
    + build `T` back up and return
* `d = 4 | v = 7 | T = [2, 4, 5, 7] | R = [8]`
    + build `T` back up and return
* `d = 3 | v = 8 | T = [2, 4, 5, 8] | R = []`
    + build `T` back up and return
* `d = 2 | v = 5 | T = [2, 4, 5] | R = []` recurse on 3
* `d = 3 | v = 3 | T = [2, 3] | R = [5, 4]` recurse on 1
    + set `5.f = 24 - 4 = 20` and `5.removal = 3`
    + set `4.f = 53 - 4 = 49` and `4.removal = 3`
* `d = 4 | v = 1 | T = [1] | R = [5, 4, 3, 2]` recurse on 0
    + set `5.f = 24 - 4 = 20` and `5.removal = 3`
    + set `4.f = 53 - 4 = 49` and `4.removal = 3`
* ...

I will not continue the rest cause it will take a while, but you can see at this point all nodes in the subtree rooted at `5` have been completely evaluated.

---

## Analysis

This is where I'm having a bit of trouble. It is technically one traversal of the tree, but I am not sure if this is $O(n + m)$. There would need to be some argument about how many times a node can be pushed and popped onto $T$ and $R$.

Consider a path $p$ from root to leaf. Every node on this path will be popped and pushed from $T$ and $R$ a constant number of times (similar argument as the linked list). Every time a node $v$ forks into $k$ children, this will increase the number of times nodes on the path from root to $v$ will be pushed and popped by a factor of $k$. When we reach the leaf node, $T$ will be empty and $R$ will be full.

You can upper bound this by the following formula. Let $k$ be the total number of leaf nodes, let $d$ be the maximum depth of the tree. Then the runtime is $O(kd)$.

To put this into perspective, for a binary tree of depth $\log n$ and $n/2$ leaf nodes, this runs in $O(n \log n)$.
> 1 votes

---
Tags: algorithms, data-structures, optimization, trees
---


# Question
Title: Proving that L(G) is the language defined by the CFG G
I have a context-free grammar defined by the production S:

S → aSbS ∣ bSaS ∣ ε

I need to prove that the CFG "G" can be defined as a language L(G) where

L(G) = {w ∈ {a, b}∗ ∶ na(w) = nb(w)}.

Where na(w) = number of a's in w, and nb(w) is the number of b's in w

How can I go about proving something like this? Is there a method?

Without giving the answer away.

# Answer
> 1 votes
Let us denote $L'$ the language defined by the CFG $S$.

To prove $L'$ = $L$ you must do two things:

1. prove $w' \in L' \Rrightarrow w'\in L(G)$, meaning $L' \subseteq L(G)$
2. prove $w \in L(G)\Rrightarrow w\in L'$, meaning $L(G) \subseteq L'$

Combine proofs 1 and 2, and you get that $L' = L(G)$.

The proofs themselves are not hard, since $L'$ has a very specific structure.

---
Tags: context-free
---


# Question
Title: Turing Machine that both halts and loops in NP
This is in regards to a specific TM:

$UNIQUE: \\{$ TM | TM loops on at least an input, and TM also halts on at least one input $\\}$

This is a play on the Halting Problem, where it basically combines $HP$ as well as $\overline{HP}$ into one. We know that $HP$ is NP-Hard, we also know that $\overline{HP}$ is NP-Hard, but would combining the two also be NP-Hard? How would the proof for this go?

# Answer
It's not only NP-hard, it's undecidable!

For the easy proof, use Rice's Theorem. This is a non-trivial semantic property, so it's undecidable (and thus NP-hard). Done.

For a more interesting proof:

For any Turing machine $T$, let's define a new machine $Z\_T$ like this:

> $Z\_T$ looks at the first symbol on the tape. If it's a `1`, it moves to the right and runs $T$ on the remainder of the tape. If it's anything else, it loops forever.

Now, suppose there exists a machine $U$ that can decide `UNIQUE`. I'm going to use this machine to decide the "Any-Input Halting Problem" ("is there any input that will make this machine halt?"), which is known to be undecidable (and NP-hard).

For any Turing machine $T$ that you give me, I can create a $Z\_T$. Then I run $U$ on $Z\_T$. I know that, for the input `0`, $Z\_T$ will loop forever. I also know that $Z\_T$ halts on input `1XYZ` only if $T$ halts on input `XYZ`. Therefore, $U$ will accept $Z\_T$ *if and only if* $T$ halts on some input.

Since we know the Any-Input Halting Problem can't be decided, this hypothetical $U$ can't exist. Therefore `UNIQUE` is also undecidable, and anything undecidable is also NP-hard.
> 2 votes

---
Tags: complexity-theory, turing-machines, np-hard
---


# Question
Title: Algorithm to convert undirected connected graph with no bridges to strongly connected directed graph
I am not sure how to go about this exactly. My attempt is find the pick an arbitrary node and run DFS, ordering each node by order of discovery. After this, You can orient each of edges so it pointing from lower order to higher order. Now I know this will create a path from one node to another, but doesn't guarantee a path from the other back to the initial. Is there any way to modify my algorithm so that it it would strongly connected and not just connected.

# Answer
Well the idea of dfs is quite good all you need to orient all edges away from the vertex that discovered them.

You will have a path from the root to each vertex since the graph is connected and the dfs will visit all vertices.

**Claim.** From each vertex you can reach the root.

**Proof.** Let $\mathcal{C}$ be the strongly connected components of the resulting graph. Let $\mathcal{G}$ be the DAG resulting from contracting the vertices in each component in $\mathcal{C}$. Also, let $C\_0 \in \mathcal{C}$ be the strongly connected component containing $r$. We have to prove that $C\_0$ is the only component in $\mathcal{C}$ and hence, it contains all the vertices in the graph. Assuming otherwise, all components must be reachable from $C\_0$ in $\mathcal{G}$, since all vertices are reachable from $r$ in $G$. choose $C$ to be a component in $\mathcal{C}$ that is the end of a longest path $P$ from $C\_0$ in $\mathcal{G}$. Let $C'$ be the component previous to $C$ on that path. There is an edge from a vertex in $C'$ to a vertex in $C$. But this edge is not a bridge, hence, there must be an edge leaving $C$ and directed from $C$ to outside $C$ (since such an edge must have been discovered the first time we visited $C$). If this edge goes to a component $C''$ not on $P$, we could have extended $P$ to $C''$ resulting in a longer path wich is a contradiction. On the other hand, if it goes to a component on $P$, it forms a cycle, which contradicts the assumption that $\mathcal{G}$ is the DAG over the SCCs of the graph we build from $G$ and hence cannot have cycles. Hence, $\mathcal{C}$ cannot have more than one component, namely $C\_0$.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Introductory Book on Pseudo-Random Number Generation
I'm a rank amateur in the area of pseudo-random number generation. I've recently found out that certain generators are better than others (e.g. mt19337 vs rand in C++) and learned what modulo bias is.

**My Request**

I'm looking for an introductory book on pseudo-random number generation. Does one exist?

**My Requirements**

The book must be understandable by someone with the following mathematics background:

* calculus
* discrete math (combinatorics, logic and proofs, set theory, mathematical induction, functions and relations, inclusion-exclusion, generating functions, recurrence relations, graphs/graph algorithms)
* linear algebra (vectors,matrix algebra, eigenvalues, transformations, diagonalization)
* introductory numerical analysis (computer arithmetic and errors, root-finding algorithms, computational techniques for matrices, numerical integration and differentiation)

I would prefer a book that does not require knowledge of any specific programming language:

* Would like algorithms to be presented in a pseudocode style (e.g. Introduction to Algorithms by Cormen)
* If the book isn't language neutral, I know the following languages: Python, Java, C++,C,Ruby.

I'm looking for a book that is accessible to a fairly inexperienced CS undergraduate:

* I have a basic understanding of stacks, linked lists, trees, heaps, hash tables and graphs
* I'm comfortable with basic programming concepts

The book should cover pseudorandom number generation at an *introductory* level:

* I'm not looking for a complete encyclopedic treatment on every research paper ever published in the area, but enough content to gain an entry level understanding in the area that you'd expect someone to learn in a first undergraduate course on pseudo-random number generation. For example if someone asked you for a book on introductory calculus you'd probably recommend a book that covers limits, differentiation, related rates, approximation of derivatives, L'Hopital's Rule and some basic continuous optimization. I'm looking for something similar in the area of PRNG. It's hard for me to specify exactly what I'm looking for because I know next to nothing about the area, but try and think of what you'd expect a complete amateur in the area to be able to reasonably learn in a semester.

**What I've Tried**

I'm looking at Chapter 3 of Donald Knuth's art of computer programming volume 2. The book seems quite old and uses some kind of assembly that I don't understand. If this is the authoritative reference, I'll find my way around these issues, but other books would be nice.

# Answer
> 2 votes
This isn't a book, and it's not a complete introduction, but Melissa O'Neill's tech report, *PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation*, doubles as one of the best surveys of general-purpose PRNGs and how to test them. It's also extremely accessible for a beginner.

It doesn't cover cryptographically strong PRNGs, so it's not a complete introduction by itself.

# Answer
> 4 votes
The book *Random numbers and computers* by Ronald T. Kneusel, recently published by Springer, contains pseudorandom number generation algorithms, evaluation techniques, and code examples in C and Python. It is aimed at "anyone who develops software, including software engineers, scientists, engineers, and students of those disciplines".

---
Tags: books, pseudo-random-generators
---


# Question
Title: Irregularity of language of prefixes of decimal expansion of pi
Let $L\_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$: $$L\_\pi = \\{3, 31, 314, 3141, 31415, 314159, \ldots\\}.$$ Prove that Lπ is not DFA-recognizable. You may use the fact that $\pi$ cannot be written as a repeating decimal, that is, there are no sequences of digits $d\_1, d\_2, \ldots,d\_m$ and $e\_1, e\_2, \ldots,e\_n$ such that

$$\pi = d\_1.d\_2\cdots d\_ne\_1e\_2\cdots e\_n=d\_1.d\_2 \cdots d\_m(e\_1\cdots e\_n)(e\_1\cdots e\_n)(e\_1\cdots e\_n)\cdots.$$

This is how I started my proof:

Proof: by contradiction.

Assume $L\_\pi = L(M)$ for some DFA $M$. We'll construct a diabolical string $x$ such that $x\notin L\_\pi$, but $M$ accepts $x$.

Let $x = d\_1.d\_2\cdots d\_ne\_1e\_2\cdots e\_n=d\_1.d\_2 \cdots d\_m(e\_1\cdots e\_n)(e\_1\cdots e\_n)(e\_1\cdots e\_n)\cdots$; clearly $x\in L$.

Go through $n + 1$ states, only $n$ states in $M\_1$ so $q\_i = q\_j$ for some $i, j$.

I based my proof off of this: https://courses.cs.cornell.edu/cs2800/wiki/images/2/29/Sp19-lec24-pumping-board.pdf

I'm stuck at the part where I'm trying to make a contradiction.

# Answer
> 4 votes
The pumping lemma tells you that, if $L\_\pi$ is regular, there is a word of the form $uvw$ such that $uv^kw\in L\_{\pi}$ for all $k\in\Bbb N$, where $|v|\>0$.

Note that if a word is in $L\_\pi$, any nonempty prefix of that word is also in $L\_\pi$. In particular, $uv^k\in L\_\pi$ for all $k\in\Bbb N$. In other words, $uv$, $uvv$, $uvvv$, $\cdots$ are prefixes of the decimal expansion of $\pi$.

So $\pi=uvvv\cdots$, which contradicts the fact that $\pi$ cannot be written as a repeating decimal.

---

Here are several exercises that describe the general situation. The first two exercises are pointed out by gnasher729's comment. The last exercise comes from Yuval's comment

**Exercise 1.** Show the set of all prefixes of the decimal expansion of a rational number is a regular language.

**Exercise 2.** Show the set of all prefixes of the decimal expansion of an irrational number is not a regular language.

**Exercise 3.** What about binary expansion? What if the base is changed to another number?

**Exercise 4.** A language is a prefix language if for any two of its words $w\_1$ and $w\_2$, either $w\_1$ is a prefix of $w\_2$ or $w\_2$ is a prefix of $w\_1$. Show that for a prefix language $L$, $L$ is regular if and only if $L$ is context-free. In particular, $L\_\pi$ cannot be context-free.

---
Tags: regular-languages, finite-automata, pumping-lemma, discrete-mathematics
---


# Question
Title: For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free
Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my professor says they aren't needed for the proof. Any help would be greatly appreciated!

This is the full question:

For any two languages $A, B$ over $\Sigma$, define $A \diamond B := \\{xy\mid x \in A, y \in B, |x| = |y|\\}$. Show that if $A, B$ are regular then $A \diamond B$ is context-free

# Answer
> 3 votes
One way to show this is as follows. Make another copy of your alphabet, $\Sigma'$. Let $B'$ be the language $B$ over $\Sigma'$. The language $AB'$ is regular. By intersecting this with an appropriate context-free language, we can get the language of all words $xy'$, where $|x|=|y'|$, $x \in A$, and $y' \in B'$. Finally, we can remove the tags, replacing $\Sigma'$ with $\Sigma$.

Another way is using grammars. Construct an automaton $D(A)$ for $A$ and $D(B^R)$ for the reverse of $B$. Construct a grammar whose nonterminals encode a pair of states $(q\_a,q\_b)$, where $q\_a$ is a state in $D(A)$ and $q\_b$ is a state in $D(B^R)$. There will be productions $(q\_a,q\_b) \to \sigma\_a (q'\_a,q'\_b) \sigma\_b$ which correspond to transitions in both automata simultaneously, and productions $(q\_a,q\_b) \to \epsilon$ for all pairs of final states.

Yet another way is using NPDAs. The NPDA first simulates an automaton $D(A)$ for $A$, pushing a symbol $X$ into the stack whenever it reads a letter. It then nondeterministically transitions to simulating an automaton $D(B)$ for $B$ (only when reaching a final state of $D(A)$!), popping a symbol $X$ from the stack whenever it reads a letter. You should arrange matters so that the NPDA accepts only if it reaches a final state of $D(B)$, and moreover exhausts the stack. (You can do this using a special symbol found at the bottom of the stack.)

I'll let you work out the details.

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


# Question
Title: What doest it mean: "computer is an intelligence amplifier"?
There is one example in Kolmogorov complexity books and related articles:

Consider we have a monkey at a typewriter and a monkey at a computer keyboard.

If the monkey types at random on a typewriter, the probability that it types out all the works of Shakespeare (assuming that the text is 1 million bits long) is about

```
p_typewriter (works of Shakespeare) ≈ 2^−1000000

```

If the monkey sits at a computer terminal, however, the probability that it types out Shakespeare is now related to the Kolmogorov complexity of the works of Shakespeare, which can be approximated by

`K(works of Shakespeare) ≈ 250000 bits`

using a program that compacts these works using 250000 bits. Then:

```
p_computer(works of Shakespeare)≈2^−K(works of Shakespeare) ≈2^−250000

```

The example indicates that a random input to a computer is much more likely to produce “interesting” outputs than a random input to a typewriter.

We all know that a computer is an intelligence amplifier...

**What actually the computer does?**

# Answer
Let's first clarify the scenario. What you're basically asking is why it is more likely to randomly write a computer program that outputs the works of Shakespeare than writing the works of Shakespeare directly.

The simple answer to this is that there are many ways to write a program that outputs a fixed string, but only one way to directly write this string. This may sound a bit strange, because there is clearly a mapping from strings that describe a computer program that outputs a string to another string (that is, the string outputted by the described program), and we could interpret a large amount of strings as descriptions of programs that outputs something. So why are the sizes different?

The reason is that these mappings are not bijective: the map from programs to strings outputted is clearly surjective, as we can output any string, but also clearly *not* injective, as there are multiple programs that output the same string. So, the set of programs must be larger than the set of strings outputted by them. That means if we sample over the set of programs, we need to sample over a much smaller set to get strings of a certain size, than if we were to sample over the strings directly.
> 1 votes

---
Tags: computability, information-theory, randomness, kolmogorov-complexity
---


# Question
Title: Is there any algorithm so it can solve stable marriage problem with incomplete preference lists
I have a slightly different formulation of the stable marriage problem. Basically, I can match one man to one woman, but the preference list is incomplete, which means that a man has expressed interest only in a subset of women and vice versa. I don't think the original Gale Shapley algorithm would work for this, if so what modifications do I need to make? If Gale Shapely does not work here, is there any algorithm to solve this? code suggestions, especially in python for this kind of problem, are very welcomed.

```
Men = [1, 2, 3, 4, 5]
Women = [a, b, c, d, e]

preferences:

men:
1: a, c, d
2: d, a, b
3: a, e, b
4: c, a, d
5: e, d, a

women:
a: 1, 3, 4
b: 4, 2, 5
c: 5, 1, 4
d: 3, 2, 1
e: 5, 3, 1

```

I need to match each man to one and only one woman

and the number of preferences allowed is fixed and less than the number of candidates.

# Answer
> 1 votes
I am not completely familiar with the problem, but maybe these couple of papers (or references therein) dealing with stable marriage with partial preferences (of which your setting could perceived as a special case) may be helpful:

https://www.math.unipd.it/~frossi/stc-care5-cr.pdf

https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6840/6488

---
Tags: algorithms, graphs, game-theory
---


# Question
Title: Turing Machine which will double every 'b' in all inputted string
I am trying to construct a Turing machine which will double every 'b' in all inputted strings over{c,b}. How can I double 'b' in inputted string? because I cannot replace b with bb because one cell of tape can contain only one character.

# Answer
> 0 votes
When you encounter $b$ change state to shifting tape right: move to next cell read content and put blank character.
Keep replacing characters until you encounter blank character (end of your tape content).
Put your last character at the end and move head left until you find blank character. Pur $b$ there.
Keep moving right until you find $b$ and repeat.

In your example:
$\color{green}cbcbcb\\\_$
Move right
$c\color{green}bcbcb\\\_$
Change state to copy and put blank:
$cb\color{green}\\\_bcb\\\_$ switch state to put $c$ and memorize next element
$cb\\\_\color{green}ccb\\\_$ switch state to put $b$ and memorize next element
$cb\\\_c\color{green}bb\\\_$ switch state to put $c$ and memorize next element
$cb\\\_cb\color{green}c\\\_$ switch state to put $b$ and memorize next element
$cb\\\_cbc\color{green}b\\\_$ blank encountered, move back to blank
$cb\\\_cb\color{green}cb\\\_$
$cb\\\_c\color{green}bcb\\\_$
$cb\\\_\color{green}cbcb\\\_$
$cb\color{green}\\\_cbcb\\\_$ blank encountered put $b$
$cbb\color{green}cbcb\\\_$ now repeat move right and switch to copy mode when another $b$ is found. When you reach end of the tape then all $b$'s are doubled.

# Answer
> 0 votes
Alternatively, use another tape to write your result on : if it is a b, write two b, otherwise juste copy the character. This works as well as having one tape because one can show that a one tape TM can simulate a k-tape TM for any fixed k.

---
Tags: turing-machines
---


# Question
Title: Is there a useful algorithm with a decreasing asymptotic time?
Algorithmic complexity is usually increasing and almost always strictly increasing based on input size. This is logical since algorithms take time to execute steps, and for almost all problems, the larger the input the more steps are needed to handle that input.

I want to know if there is an algorithm that does not increase with input size but rather decreases.

You could make an algorithm with decreasing asymptotic time by for example, making it loop -n + 10000 times, where n is the size of an array of integers.

This however doesn't do anything other than cycling, it shows that you could make such an algorithm, if the algorithm doesn't do anything useful. Is there an algorithm that decreases asymptotically as the size of the input increases, that solves an actual problem (theoretical or other)?

EDIT:

Some people seem to be getting confused by the question so i want to clarify.

Is there a non-trivial algorithm that executes less steps as the size of the input increases?

# Answer
No. If the running time is approaching zero as the input size grows, then the algorithm can’t even perform a single step.

If you mean that the running time approaches some positive constant, then this is just $O(1)$, because $\Omega(1)$ is a lower bound for any algorithm.
> 6 votes

# Answer
I think everyone knows useful algorithms with constant complexity, e.g. test if a number is even by checking the last bit, or negative by checking the sign bit. You might need to argue for a random access model to the input if you can't guarantee you see the start or end of the stream first (big/little endian issues) but still one of these is valid and used all the time. That is not strictly decreasing but it does, as asked, solve a useful problem with a subset of the input.

But there are many reasonable algorithms with such features. Take a Monte Carlo algorithm that learns how much white space is in a document. It can sample less and less of a larger document and still have reasonable statistics. Polling data is this way too.

Also consider machine learning. When I worked on natural language recognition years back we found you don't keep training on equal proprotions of data, you can reduce the amount you sample as you get a larger corpus to study. I'd call that a form of "decreasing".

---

I think the main issue is as Raphael mentioned the word "complexity" which invites a purely asymptotic tone. If so you ignore any changes in behavior before some constant size $B$. And so to be a decreasing function from that point on would be hard to do meaningfully. But what about a function like $O(n^{1/n})$, doesn't that have some meaningfully "decreasing" complexity without being a strictly decreasing function?

I would argue that decreasing has a natural interpretation that is meaningful, e.g. that an algoirthm in some initial range behaves quadratically, but in large enough inputs can become linear.

A real life example of what I mean is matrix multiplication. The complexity by Coppersmith-Winograd is around $O(n^{2.3})$ but it takes a very large $n$ to get to that complexity. So in reality we model it something like $O(n^3)$ for $n\<100$, swapping to $O(n^{2.7})$ for some regime $100\leq n\leq 1,000,000$, and perhaps some other complexities after that all the way until we hit the extreme regime. (Yes experts, those ranges are hypothetical for illustration, not the result of citing some specific test suit!)

That I would argue is a form of "decreasing" complexity and found quite often in useful algorithms.
> 0 votes

---
Tags: algorithms, complexity-theory, runtime-analysis
---


title: Pumping lemma for regular languages

text:
# Question
Title: Pumping lemma for regular languages
I have a vey specific question regarding the pumping lemma in the context of regular languages. The theorem states that if $L$ is a regular language, then there exists a constant $n$ such that for every string $w$ in L, with $|w|\geq n$, $w$ can be broken into $w=xyz$ with the following properties:

1. $|y|\>0$
2. $|xy|\leq n$
3. For all $k\geq 0$, $xy^kz \in L$

My question concerns the third and first properties. In the third property, does $k=0$ not imply that $|y|=0$, therefore contradicting the first property? As far as I can tell, when $k=0 \rightarrow xy^kz=xz$ and, consequently, $y=\epsilon$. What am I missing?

# Answer
How long is the word "cat"?

If I write "catcat", how long is the word "cat"?

If I write nothing at all, how long is the word "cat"?
> 4 votes

# Answer
> In the third property, does $k = 0$ not imply that $|y| = 0$ , therefore contradicting the first property?

**No, it does not.**

The third item simply implies $w' = xz \in L$. If $|w'| \< n$, then this does not contradict the lemma since it only holds for strings with length at least $n$. On the other hand, if $|w'| \ge n$, it means there are again substrings $x', y', z'$ with the conditions prescribed in the lemma (i.e., $|y'| \> 0$, $|x'y'| \le n$, and $x'(y')^k z' \in L$ for all $k \ge 0$), but it *does not at all imply* $x = x'$, $y = y'$, nor $z = z'$, let alone $w' = w$.
> 3 votes

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: How do I describe formally complexity of 2-sum problem algorithm?
I have algorithm that finds if there are two elements in sorted array that have sum zero.

```
1.ZeroSumPair(A[1..n]) // A[1..n] <-- sorted
2.    l <- 1, r <- n
3.    while(l < r)
4.        while(l < r or A[l] + A[r] > 0)
5.            r--
6.        if(A[l] + A[r] = 0)
7.            return true
8.        l++
9.    return false

```

Intuitively I know that this algorithm is $O(n)$, but how do I deduct it using proof with summations like in CLRS book?

I've also saw How to develop an $O(N)$ algorithm solve the 2-sum problem?, but I didn't see any formal proof.

# Answer
> 2 votes
Consider this slightly modified algorithm where I've added an "operation counter" `t`. This will be incremented every time we do a comparison or assignment.

```
1. ZeroSumPair(A[1..n]) // A[1..n] <-- sorted
2.   l <- 1, r <- n
3.   t <- 3             // 2 for first two assignments and 1 for initial while check
4.   while(l < r)
5.     t++              // 1 for initial while check
6.     while(l < r or A[l] + A[r] > 0)
7.       t++            // 1 for decrementing r
8.       r--
9.       t++            // 1 for following while check
10.    t++              // 1 for if comparison
11.    if(A[l] + A[r] = 0)
12.      return true
13.    t++              // 1 for incrementing l
14.    l++
15.    t++              // 1 for following while check
16.  return false

```

This is a bit verbose, but it will work. Now we must simply prove that, at termination we have $t = O(n)$. We can do this inductively with a loop invariant.

Let's use the following loop invariant for the loop on line 4.

$$t = 3 + 4(l-1) + 2(n-r)$$

### Base Case

Initially $t = 3$, $l = 1$, and $r = n$. Thus we have:

$$3 = 3 + 4(1 - 1) + 2(n - n) = 3$$

### Inductive Case

Let $t'$, $l'$, and $r'$ be the values of $t$, $l$, and $r$ at the end of our previous iteration. At the end of our current iteration we have $l = l' + 1$, $r = r' - k$ for some $k$, and $t = t' + 4 + 2k$. Thus we have:

$$\begin{align\*} t & = t' + 4 + 2k\\ & = 3 + 4(l' - 1) + 2(n - r') + 4 + 2k\\ & = 3 + 4(l - 2) + 2(n - (r + k)) + 4 + 2k\\ & = 3 + 4(l - 1) - 4 + 2(n - r) - 2k + 4 + 2k\\ & = 3 + 4(l - 1) + 2(n - r) & \square \end{align\*}$$

Thus, we can conclude the loop invariant holds. At the end of the loop (in the worst case) we have $l = r \leq n$. We then have: $$\begin{align\*} t & = 3 + 4(l - 1) + 2(n - r)\\ & = 3 + 4l - 4 + 2n - 2l\\ & = 2(n + l) - 1\\ & \leq 2(n + n) - 1\\ & = 4n - 1\\ & = O(n) & \square \end{align\*}$$

Thus it is linear. There might be an easier way to do this, but this way makes sense to me pretty clearly.

---
Tags: algorithms, algorithm-analysis, asymptotics
---


# Question
Title: Can an artificial neural network convert from cartesian coordinates to polar coordinates?
Given cartesian coordinates $x$ and $y$ as input, can a neural network output $r$ and $\theta$, the equivalent polar coordinates?

This would seem to require an approximation of the pythagorean theorem (which requires approximations of $x^2$ and $\sqrt{x}$) and $\sin$, $\cos$, or $\tan$ approximations. Is this possible?

If so, how many hidden layers would it take? I'm using an LSTM.

# Answer
i dont know if this answers your question (or at least part of it)

According to the Universal approximation theorem for ANNs, it is possible (at least within a region of interest).

The question about how many hidden layers (and architecture) an ANN should have, is, AFAIK, an open problem, in the sense that there is no result to determine architecture and/or number of layers wrt specific final results (partly, this is due to the non-constructive proof of the above result), although you might want to see here and here.

Here is a review on methods to fix number of hidden layers in ANNs during the past 20 years: Review on Methods to Fix Number of Hidden Neurons in Neural Networks

Most ANNs are built by a trial and error process.

*update (just an idea)*

By modeling the transformations from cartesian to polar (and approximating square roots,..) as a discrete system, maybe one can transfer this design into ANN model (but i wont pursue this further right now)
> 2 votes

# Answer
From what I learned from my teacher at UCSD, Prof. Sebald, a 3 layer neural network is a universal function approximator. The first layer draws lines in the sand (hyperplanes). It performs dichotomies. The second layer does AND'ing and OR'ing of those half-planes into convex sets (DeMoivre Theorem stuff). The 3rd layer forms inclusions/exclusions of convex sets at which point you can represent any time of non-convex shape. So honestly, this question is not about whether or not it's possible. It's about the difficulty. That expresses itself in terms of a) the domain of convergence where a neural network is able to get close to the right answer (generalization capability) and b) how big the network has to be. And finally, there ends up being far more in-fighting between the nodes of a neural network that is shallow and wide... When the neural network has no more free parameters than the inherent dimension of the data, it becomes very hard to train. So the huge success of deep learning is about a) adding many more parameters (ie layers) to give a lot more capacity to the problem than is inherently needed and b) then regularize by adding a complexity-penalty (Lagrange multiplier) to each parameter. So that every parameter in the network has to add more performance than the complexity penalty costs. That way it sorts the parameters so that the highest-value ones stay and the lowest-value ones are driven out of the network.
> 1 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: Are all hypothetical machine models for calculating runing time of an alogrithm same?
Im learning about time complexity analysis, and cant seem to figure out why do we consider a hypothetical machine that takes 1 unit of time for arithemitic and logical instructions and 1 unit of time to for assignment and return statements.

**Q)** why does it have to be 1 unit of time?

**Q)** Also is it upto to the analyzer to define such parameters for hypotheical machine models or is there some sort "standard/convention" used instead ?

# Answer
In RAM model, which is very close to our computers, standard arithmetic operations and assignments take same time disregarding values as far as they fit to computer word. This yields good estimate for runtime and apgorithm behaviour. When some operation takes $c$ time, but constant you may provide it in assymptotic analysis or omit it, becase such analysis takes into consideration length of the input as it grows.

For fine grained computation and small inputs it makes sense to check whether $\mathcal O(5n^2)$ is better than $\mathcal O(100n)$. In assymptotic case constants are dominated by input length, that is why there is no difference between 3 and 20000, so using 1 as time unit makes calculations easier.

It is up to analyzer, how fine grained is analysis, but also which model is chosen, differences here are huge. Between RAM model and Turing Machine model difference is polynomial. Between RAM and Real RAM or BSS machine are vast, instead of word-sized integers arbitrary real or respectively rational numbers could be stored with operations on them taking single time unit. This creates enormous computation gap. So the choice of model is crucial and models are nowhere near similar.

Convention is to use smallest plausible model.
If you sort integers in transdichotomous model, the size of numbers doesn't matter, in RAM it does, it takes unit cost if they fit word size or longer if they don't.
> 0 votes

---
Tags: time-complexity, runtime-analysis
---


title: Implications of $NL=P$

text:
# Question
Title: Implications of $NL=P$
What would be some implications of $NL$$=P$? Would it be possible to get recommendations on good sources/papers I can read to learn more about this? Thank you

# Answer
$NL = P$ means that every language in $P$ can be decided by a nondeterministic Turing machine using at most $O(\log n)$ space, where $n$ is the size of the input.

Savitch's theorem states for all $f(n) \in \Omega(\log n)$: $NSPACE(f(n))\subseteq SPACE(f(n)^2)$.

Therefore $NL = P$ implies that every language in $P$ can be decided by a deterministic Turing machine using at most $O((\log n)^2)$ space.
> 1 votes

---
Tags: complexity-theory, reference-request, nondeterminism
---


# Question
Title: Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)?
Suppose we have a function $f$,

$$ C = f(A,B), $$

where $A$, $B$ and $C$ are random variables.

I notice that when the random variables are binary ($\\{0, 1\\}$) and $f$ is the XOR operation, we have the following identity:

$$ H(C|A) = H(B), $$

where $H(B)$ is the entropy of $B$ and $H(C|A)$ is the conditional entropy of $C$ given $A$.

Obviously this is not true for a general $f$. What I am interested to know is, is there a set of conditions on $f$ and $A,B,C$, under which the identity above holds.

# Answer
> 4 votes
The following answer assumes that $A,B$ are independent, and that $A,B$ have full support on their respective domains (the latter is without loss of generality). For the general case, see the other answer.

Let's write your equation in a slightly different way: $$ H(B) = H(f(A,B)|A) = \operatorname\*{\mathbb{E}}\_{a \sim A} H(f(a,B)). $$ Clearly $H(f(a,B)) \leq H(B)$, with equality if and only if $f(a,b\_1) \neq f(a,b\_2)$ whenever $b\_1 \neq b\_2$. We deduce that $H(B) = H(f(A,B)|A)$ if and only if $f$ is injective in its second argument, i.e., for all $a$ and $b\_1 \neq b\_2$, we have $f(a,b\_1) \neq f(a,b\_2)$.

# Answer
> 8 votes
Note

\begin{align} 0&=H(C|A,B)\\ &=H(A,B,C)-H(A,B)\\ &=H(B|A,C)+H(C|A)+H(A)-H(A,B)\quad\text{(chain rule)}\\ &=H(B|A,C)+H(C|A)-H(B|A), \end{align}

so $H(C|A)=H(B)$ is equivalently $H(B|A,C)+H(B)-H(B|A)=0$. Also note $H(B|A,C)\ge 0$ and $H(B)\ge H(B|A)$, your condition is equivalently $H(B|A,C)=0\wedge H(B)=H(B|A)$.

For a human-readable explanation, $H(B|A,C)=0$ means $B$ is determined by $A$ and $C$, that is, for any fixed $a$ in the support of $A$, $f(a,b)$ as a function of $b$ with domain $\\{b\mid \mathrm{Pr}\\{A=a, B=b\\}\>0\\}$ is an injection. $H(B)=H(B|A)$ means $A$ and $B$ are independent of each other.

---
Tags: information-theory
---


# Question
Title: How to represent calculable real numbers?
Suppose I want to do arithmetic without any loss of precision. Floats and doubles are inappropriate. I want to use dynamic memory allocations to store any real number obtained after a finite amount of finite operations (addition, subtraction, multiplication, division), starting from natural numbers without ever losing the slightest chunk of the result.

This means, I don't care at all about Pi or the square root of 2, because I have no finite method to obtain them in the first place. I don't want to apply any transcendental function either (cos/sin) because by definition they would never end.

Intuitively, it is obvious that 1/3 cannot be stored in base 2 or 10 using a finite amount of memory (0.33333...), therefore a correct representation would have to be at least fractional.

If this is possible, surely there must be some software out there who already does this. What would be the standard way to go? Preferably, I want a fast (hardware-accelerated) solution, for example using words as digits instead of bits.

# Answer
> 2 votes
A number is obtained from natural numbers using addition, subtraction, multiplication, or division if and only if it is rational. You can store rational numbers as pairs $(p,q)$ of integers, which represent the number $p/q$ (so $q \neq 0$). You can further assume that $p,q$ are mutually prime.

Libraries implementing rational numbers using arbitrary-precision integers are available, for example GMP.

---
Tags: arithmetic
---


# Question
Title: Prove/disprove - reverse topological sort transpose graph
I need to prove or disprove the following statement:

***"Let $G$ be a directed acyclic graph, and $v\_1v\_2...v\_k$ a topological sort of $G$. Then $v\_kv\_{k-1}...v\_1$ is a valid topological sort of the transposed graph $G^T$."***

(The algorithm used is the one presented in CLRS 22.4)

I think the statement is **correct**.

My logic is that for every two vertices $v\_i,v\_j$ s.t $v\_i\<v\_j$ in the sorting of $G$, one of two conditions hold:

A) $v\_j$ is a decedent of $v\_i$ in $G$, so in every topological sort of $G$, $v\_i$ will be before $v\_j$ in the sort.

B) or there's no path from $v\_i$ to $v\_j$ or the contrary, so $v\_i$ and $v\_j$ can switch places in the sorting, depending on the order that the DFS run on $G$.

From here, if condition A held then in the sorting of $G^T$, $v\_j\<v\_i$, because now there's a path from $v\_j$ to $v\_i$, and if condition B held, then the order $v\_j\<v\_i$ is valid for some topological sort of $G^T$. And so the sorting $v\_kv\_{k-1}...v\_1$ is valid sort of $G^T$.

Something still doesn't feel right about this... would appreciate any help or comment.

# Answer
A topological sort of a graph $G$ is an order $\pi$ such that if there is a directed path from $x$ to $y$ in $G$, then $x$ precedes $y$ in $\pi$.

Let us now show that $\pi^R$ is a topological sort of $G^R$. If there is a path from $x$ to $y$ in $G^R$ then there is a path from $y$ to $x$ in $G$, and so $y$ precedes $x$ in $\pi$, and so $x$ precedes $y$ in $\pi^R$.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Lemma R of section 3.2 (The Art of Computer Programming)
In "The Art of Computer Programming" by Donald Knuth, the proof of lemma R starts with the assumption that $\lambda = p^e$ which means:
$$\left({a^{p^e}-1\over a-1}\right)\equiv 0\pmod{p^e}$$ The above condition leads to: $$a\equiv1\pmod{p^e}\quad(1)$$ Knuth also considers the case when $p=2$ and $a\equiv3\\;(\operatorname{mod} 4)$.We then have: $$(a^{2^{e-1}}-1)/(a-1)\equiv 0\pmod{2^e}$$ Or: $$a^{2^{e-1}}\equiv a^{2^e}\pmod{2^e}$$ He then writes:

> These arguments show that it is necessary in general to have $a=1+qp^f$,where $p^f\>2$ and $q$ is not a multiple of $p$, whenever $\lambda=p^e$

I have two questions here:

1. *Why would we need to consider the case when $p=2$ and $a\equiv3\pmod4$?*
2. *What proves $a=qp^f+1$?*

# Answer
> In "The Art of Computer Programming" by Donald Knuth, the proof of lemma R starts with the assumption that $\lambda = p^e$ which means:
> $$\left({a^{p^e}-1\over a-1}\right)\equiv 0\pmod{p^e}$$ The above condition leads to: $$a\equiv1\pmod{p^e}\tag 1$$

If you read more carefully, that condition does not lead to formula (1). It only leads to $$a\equiv1\pmod{p}\tag{2 }$$ In the case of $p=2$, the above condition is $$a\equiv1\pmod{2}\tag{3 }$$ which falls short of $$a\equiv1\pmod{4}\tag{4 }$$ That is why Knuth has to exclude the case of $a\equiv3\pmod{4}$ before asserting the formula (4).

> What proves $a=qp^f+1$, where $p^f \> 2$?

Formula (2) implies $a=qp^1+1$ for all $p\>2$, where $p^1=p\>2$ in. Formula (4) implies $a=q4+1$ when $p = 2$, where $4=2^2\>2$.
> 1 votes

---
Tags: algorithm-analysis
---