title: Number of equivalence classes

text:
# Question
Title: Number of equivalence classes
Given language $L$, why is it not necessarily true that the number of equivalence classes of $L$ is equal to the number of equivalence classes of $L^R$?

And for the private case that $L$ is regular, is that true?

# Answer
Assuming you refer to Myhill-Nerode equivalence classes:

First notice, that for a non-regular language $L$, the number of classes is necessarily infinite. This is one direction of the Myhill-Nerode theorem.

Since regular languages are closed under reversal, it follows that for a non-regular language $L$, both $L$ and $L^R$ have the same \`\`number'' (namely, infinitely) of equivalence classes.

For the case of regular languages, the Myhill-Nerode relation is very \`\`right-biased'', since it relates to the existence of a separating *suffix*. This is why reversing the language may change the number of classes. For example, consider the language

$$L\_k=\\{w\in \\{a,b\\}^\*: w\_k=a\\}$$ i.e. the language of words whose $k$-th letter is $a$.

It's easy to show that the number of classes for $L\_k$ is roughly $k$ (maybe $\pm 1$).

However, the language $L\_k^R$ of words whose $k$-before last letter is $a$, is known not to have a DFA with less than $2^{k-1}$ states (and hence it has $\Omega(2^k)$ classes).

Interestingly, reversal and congruence classes do have an interplay: if you take a DFA, reverse it, determinize it, reverse it again, determinize again, and remove all unreachable states, you will obtain a minimal DFA for the original language, which is exactly what the equivalence classes characterize. This is Brzozowski's algorithm.
> 2 votes

---
Tags: formal-languages, turing-machines, regular-languages
---


# Question
Title: Clarifying $\sum_{h=0}^{\lfloor lg(n)\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n)\rfloor}\frac{h}{2^h})$ in BUILD-MAX-HEAP
I was going the text Introduction to Algorithms by Cormen et. al. Where I came across a step in the analysis of the time complexity of the $BUILD-MAX-HEAP$ procedure.

The procedure is as follows:

```
BUILD-MAX-HEAP(A)
1   heap-size[A] <- length[A]
2   for i <- ⌊length[A]/2⌋ downto 1
3       MAX-HEAPIFY(A,i)

```

Now the authors claim to derive a tighter bound by observing that the time for $MAX-HEAPIFY$ to run at a node varies with the height of the node in the tree, and the heights of most nodes are small. The tighter analysis relies on the properties that an $n$-element heap has height $\lfloor lg (n)\rfloor$ and at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of any height $h$.

So,$$\sum\_{h=0}^{\lfloor lg (n)\rfloor} \lceil \frac{n}{2^{h+1}} \rceil O(h)= O(n \sum\_{h=0}^{\lfloor lg (n)\rfloor} \frac{h}{2^h}) \ldots \tag 1$$

Now it is in the above step that I am facing the problem. **How are the authors getting the expression on the RHS using the LHS so simply(as if intuitively).** However I do not seem to share the same intuition.

Now the maximum height of any node is the height of the root which is $\lfloor lg (n)\rfloor$. Now let us find a bound for the minimum possible value of the fraction $\frac{n}{2^{h+1}}$ ,which occurs when $h=\lfloor lg (n)\rfloor$

So, $$\frac{n}{2^{\lfloor lg (n)\rfloor+1}} = \frac{n}{2.2^{\lfloor lg (n)\rfloor}}\geqslant\frac{n}{2.2^{lg (n)}}=\frac{n}{2n}=\frac{1}{2} \ldots \tag 2$$

Now from the analysis step by the authors in (1) they are assuming

$$\lceil \frac{n}{2^{h+1}} \rceil \leqslant c.\frac{n}{2^h}, c\>0 $$

Now as far as I know from mathematics,

$$\lceil \frac{n}{2^{h+1}} \rceil \lt \frac{n}{2^{h+1}}+1$$

And for the way the authors worked out , it must be the situation as below,

$$\lceil \frac{n}{2^{h+1}} \rceil \lt \frac{n}{2^{h+1}}+1 \leqslant c.\frac{n}{2^{h}}$$

So, $$\frac{n}{2^{h+1}}+1 \leqslant c.\frac{n}{2^{h}}$$

$$\iff 1 \leqslant c.\frac{n}{2^{h}}-\frac{n}{2^{h+1}}$$

$$\iff 1 \leqslant \frac{n}{2^{h+1}}(2c-1)$$

$$\iff \frac{n}{2^{h+1}}\geqslant \frac{1}{2c-1} \ldots \tag 3 $$

Now for (3) to comply with (2) we should have,

$$2.c-1 \geqslant 2 \iff c \geqslant \frac{3}{2}$$

Now is that single line in (1) worth this much effort or is it the situation that the step is trivial or intuitive that we can just mentally do the step. If it is the latter, please enlighten me with such intuition..

Even in this answer here that $\frac{n}{2^{h+1}}\lt\frac{n}{2^{h}}$ is intuitive but that $1\lt\frac{n}{2^{h}}$ is not quite intuitive and requires the use of (2) I feel

# Answer
> 2 votes
Since $h \leq \lfloor \lg n \rfloor$, we have $2^h \leq n$, and so $n/2^{h+1} \geq 1/2$. Therefore $$ \left\lceil \frac{n}{2^{h+1}} \right\rceil \leq \frac{n}{2^{h+1}} + 1 = \frac{n}{2^{h+1}} + 2 \cdot \frac{1}{2} \leq \frac{n}{2^{h+1}} + 2 \frac{n}{2^{h+1}} = 3 \frac{n}{2^{h+1}}. $$ (In fact, if you are more careful then you can replace $3$ by $2$.)

More generally, if $x \geq c \> 0$ then $\lceil x \rceil = O(x)$, where the hidden constant depends on $c$.

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


# Question
Title: Turing Machine construction of M=wwRw form
Construct a Turing machine for `M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}`.

I tried to imagine that I will have to divide the string into 3 equal parts and check if the first and last part are identical, and that first two parts form a palindrome. But not sure how to proceed with this to construct the turing machine.

# Answer
So, I can grant that your idea is right. Divide the string into 3 equal parts; for example, if you have `aabbaaaab`, divide the strings like this: `aab baa aab`. In case it isn't possible, directly reject it. Otherwise for the next step, check if the concatenation of the first two substrings forms a palindrome; if it doesn't, stop and reject, but if so, then proceed further. In the last step, just check if the first and last substrings match, if so, accept, else reject. With all these in mind, the following should work:
> 0 votes

---
Tags: formal-languages, turing-machines, automata, regular-expressions, pushdown-automata
---


# Question
Title: Find position in array where element-wise multiplication with string of 1 and 0s results in max value
I have a sequence of 1s and 0s. For example: $bits = \[1, 0, 1, 1, 1, 0\]$. I also have an array of positive integers. For example $arr = \[12, 23, 4, 6, 8, 0, 24, 72\]$. I need to find the index, $i$, in $arr$ of the leftmost element of $bits$ such that

$$\sum\_{j = i}^{i + \textrm{length of bits}}{bits\[j - i\] * arr\[j\]}$$

is a maximum. Essentially I am maximizing the element-wise multiplication between the two sequences starting at index $i$.

I need to solve it in $O(n\log n)$ or better, but I can only think of a way to do it in $O(n^2)$. I have a feeling prefix sums could be used but am not sure how.

# Answer
Let the array consist of the numbers $a\_0,\ldots,a\_{n-1}$, and let the mask be $b\_0,\ldots,b\_{k-1}$. Define $$ A = \sum\_i a\_i x^i, \quad B = \sum\_j b\_j x^{k-1-j}. $$ Notice that $$ AB = \sum\_{i,j} a\_i b\_j x^{i+k-1-j}, $$ and so the coefficient of $x^{i+k-1}$ in $AB$ is $$ \sum\_{j=i}^{i+k-1} a\_j b\_{j-i}. $$ Therefore if you can calculate $AB$, you can solve your problem.

You can calculate $AB$ in $O(n\log n)$ using FFT.
> 1 votes

---
Tags: algorithms, optimization, arrays, big-o-notation
---


# Question
Title: Do there exist fast multiplication algorithms for two integers with one of them being static?
Let N and M be arbitrary 1024+ bit integers.

The objective is to compute the product of N and M (2048+ bits)

There exist various multiplication algorithms for various bit lengths (ex library: GMP). But there is always the assumption that both numbers are equally arbitrary.

Are there algorithms that are even faster under the assumption that for every time N changes, M changes K times with K being 2^20 or more?

An algorithm that given an integer, constructs/primes a special fast algorithm to compute a product just for that integer.

The only algorithm of this kind that I was able to find and that gave rise to this question is described in this paper: https://sci-hub.tw/10.1007/s00224-020-09986-5

C code provided by the author (GMP lib): http://www.fit.vutbr.cz/~ibarina/tmp/n.c

Summary: Uses the Collatz conjecture to do multiplication, O(Nk) where k is the number of odd integers in the Collatz sequence of a given odd operand. If k \< log N it can beat current state of the art multiplication algorithms.

# Answer
> 1 votes
If $N$ is fixed (at least for a very long time), why not do some pre-computation. For example, you can pre-compute the product of $N$ with any 16-bit integer. Just save these values in a lookup table (there are only $2^{16} = 65536$ elements). Represent $M$ in base $2^{16}$. i.e. $M = a\_0 + a\_1 * 2^{16} + a\_2 * 2^{32} \ldots a\_{63}(2^{16})^{63}$. Well, $M = (N * a\_0) + (N * a\_1) * 2^{16} + (N * a\_2) * 2^{32} \ldots ( N * a\_{63}) * (2^{16})^{63}$. Instead of computing $N * a\_i$, we can search the lookup table.

---
Tags: algorithms, integers, multiplication
---


# Question
Title: Is it correct or incorrect to say that an input say $C$ causes an average run-time of an algorithm?
I was going through the text Introduction to Algorithm by Cormen et. al. where I came across an excerpt which I felt required a bit of clarification.

Now as far as I have learned that that while the *Best Case* and *Worst Case* time complexities of an algorithm arise for a certain physical input to the algorithm (say an input $A$ causes the worst case run time for an algorithm or say an input $B$ causes the best case run time of an algorithm , asymptotically), but there is no such physical input which causes the average case runtime of an algorithm as the average case run time of an algorithm is by it's definition the runtime of the algorithm averaged over all possible inputs. It is something I hope which only exists mathematically.

But on the other hand inputs to an algorithm which are neither the best case input nor the worst case input is supposed to be somewhere in between both the extremes and the performance of our algorithm is measured on them by none other than the average case time complexity as the average case time complexity of the algorithm is in between the worst and best case complexities just as our input between the two extremes.

Is it correct or incorrect to say that an input say $C$ causes an average run-time of an algorithm?

The excerpt from the text which made me ask such a question is as follows:

> In context of the analysis of quicksort,
>
> In the average case, PARTITION produces a mix of “good” and “bad” splits. In a recursion tree for an average-case execution of PARTITION, the good and bad splits are distributed randomly throughout the tree. Suppose, for the sake of intuition, that the good and bad splits alternate levels in the tree, and that the good splits are best-case splits and the bad splits are worst-case splits. Figure(a) shows the splits at two consecutive levels in the recursion tree. At the root of the tree, the cost is $n$ for partitioning, and the subarrays produced have sizes $n- 1$ and $0$: the worst case. At the next level, the subarray of size $n- 1$ undergoes best-case partitioning into subarrays of size $(n-1)/2 - 1$ and $(n-1)/2$ Let’s assume that the boundary-condition cost is $1$ for the subarray of size $0$.
>
> The combination of the bad split followed by the good split produces three sub- arrays of sizes $0$, $(n-1)/2 - 1$ and $(n-1)/2$ at a combined partitioning cost of $\Theta(n)+\Theta(n-1)=\Theta(n)$. Certainly, this situation is no worse than that in Figure(b), namely a single level of partitioning that produces two subarrays of size $(n-1)/2$, at a cost of $\Theta(n)$. Yet this latter situation is balanced!

# Answer
The average-case running time of an algorithm with respect to some distribution $D$ is, *by definition*, the expected running time of the algorithm when run on an input sampled according to $D$.

This should be contrasted with *worst-case running time*, which is the maximum running time on *any* input of a given length, and *best-case running time*, which is the minimum running time on any input of given length.

Since worst-case and best-case running time are defined as maximum and minimum, there are inputs attaining them. Average-case running time is an expectation, and so it is meaningless to talk about an input attaining them.

If you throw a die, the expected number you get is 3.5. This is not attained by any particular throw. If the die had 5 sides, the expected number is 3, which does correspond to some throw, but that doesn't mean that the throw is "average case".

---

What sometimes happens is that you can isolate a class of inputs $X$ such that when run on an input from $X$, the running time of the algorithm is within a constant factor of the average-case running time (for this to make sense, $X$ should actually corresponds to a sequence $X\_n$ of inputs of every length, or at least infinitely many length). You can say that $X$ "achieves" the expected running time of the algorithm.
> 1 votes

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


# Question
Title: Binary subtraction with numbers in 2's complement
How can i perform binary subtraction of two numbers that are already in 2's complement? I have to subtract 01010011 from 10100110,both numbers are in 2's complement. I know that 10100110 is -90,and 01010011 is 83,so the result should be -173. So if i use 8 bits that means that there's overflow. But i don't get how can i perform the subtraction when both the numbers are in 2's complement. If i just perform the subtraction i get the same number 01010011. How do i show the result and that there's overflow?

# Answer
You cannot represent –173 using 8 bits, since the range is –128 to 127.

To subtract two numbers in two's complement, you use the identity $a - b = a + (-b)$. In your case, $a = 10100110$, $b = 01010011$, and $-b = 10101101$. Adding $a$ and $-b$, there is overflow, so you know that the number is outside the range.
> 1 votes

# Answer
You need to subtract 01010011 from 10100110.

10100110 - (01010011)

So find the 2's complement of 01010011 which is 10101101 and just add it to 10100110

```
 01011000   <=carry bits

 10100110
+10101101
----------
101010011 <= Result, but the extra 9th bit to the left of MSB is stored outside a register in a special carry out flip-flop

```

Now the carry-in and carry out of the MSB of the 8 bit register are different and so the result is overflow... (the carry in is 0 ,above the two 1's in the MSB and the carry out is 1 which is left to the MSB in the result)

If and only if the XOR of the carry-in and carry-out of the MSB is 1 then overflow.
> 1 votes

---
Tags: arithmetic, binary
---


# Question
Title: Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP?
In the book 'Computational Complexity' by Arora and Barak the following question is posed (exercise 2.20.):

> Let REALQUADEQ be the language of all satisfiable sets of quadratic equations over real variables. Show that REALQUADEQ is NP-complete.

I know how to show NP-hardness, but I'm stuck when it comes to proving that this problem is in NP, in particular how to show that we can describe a solution using a polynomial number of bits.

I did some research and found out that over the complex numbers, it remains an open question if the problem is in NP \[1\]. It also seems closely related to the existential theory of the reals, which again is not known to be in NP.

Thus my question: Is this problem known to be in NP? And if so, could somebody point me in the right direction regarding the proof.

---

\[1\] Pascal Koiran, Hilbert’s Nullstellensatz is in the Polynomial Hierarchy, Journal of Complexity 12 (1996), no. 4, pp. 273–286.

# Answer
This problem (usually called QUAD) is in fact *complete* for the existential theory of the reals, and thus showing NP-membership would be a fantastic and unexpected result. It seems that Arora and Barak intended only to ask for a proof of NP-hardness.
> 2 votes

---
Tags: complexity-theory, polynomials
---


# Question
Title: Decide if a string is a member of a language that represents $P$?
For some enumeration of the complexity class P (such as this as an example: How does an enumerator for machines for languages work?), for each string in the enumeration, does there exist some other string (certificate) that allows you to verify is a member of the enumeration in poly time? I believe that it might be possible in poly time because all we have to do is check if a string fits some certain format (format of the encoding)?

A decision problem $P$ is poly time verifiable iff there is an algorithm called verifier such that if $P(w)=$ then there is a string $c$ s.t. $(w,c)=$, if $P(w)=$ then for all strings $c$, $(w,c)=$ and V runs in $O(w^{k})$ for some constant $k$ for all inputs $w$.

# Answer
I think you can force the enumeration to be only on machines with a very strict format: a hard-coded poly time "clock" at the start, and after that the rest of the TM.

This will allow you to check in poly time (not even requiring a verifier) whether a given string $p$ is a part of the enumeration
> 1 votes

---
Tags: polynomial-time, semi-decidability, enumeration
---


# Question
Title: Meaning of the "why not" modality from linear type theory?
In linear type theory there is a modality written `!` where `!T` can be read as "infinite copies of `T`".

According to ncatlab, there is a dual to this modality which is sometimes written `?T` and referred to as the "why not" modality. What is the meaning of this modality? How does `?T` behave as a type?

# Answer
> 2 votes
First off, one thing I'd recommend is reading Filinski's Linear Continuations for ideas on how to interpret linear connectives (note, the ? modality got typeset as Γ in that for some reason).

In that paper, he uses the modality as part of the interpretation of call-by-name into linear logic. The idea is that you can kind of think of the non-modal types $T$ as being total, while $?T$ adds the possibility of divergence. If you want an analogue of "infinitely many copies of $T$", then it's, "zero or one $T$".

But of course, it's not like $1 + T$. It's more like a partiality monad living in an otherwise total language.

# Answer
> 2 votes
From a resource interpretation,

* If you receive a `!T`, you can extract as many copies of `T` as you need in your thread.

However, if you want to produce a `!T`, you need to be prepared to fulfill an unknown number of `T`s in parallel, so whatever ingredients you use would need to be `!` as well. If you have additional ⅋-threads to help you produce things, they would be `?` since they might produce an unknown number of by products.
* You can produce as many copies of `T` as you want in your thread and coalesce them all into a `?T`.

However, if receive a `?T`, you need to anticipate an unknown number of `T`s arriving in parallel. Whatever ingredients you use would become `!` and whatever you produce would also be afflicted with `?` since you might produce arbitrary copies of them in parallel.

---
Tags: type-theory, modal-logic
---


# Question
Title: "Given an algorithm, decide whether it runs in polynomial time" is this problem in NP?
This problem is not decidable (reducible to halting problem) but is semi-decidable and therefor verifiable (as those two definitions are equivalent: How to prove semi-decidable = verifiable?).

However, is this problem poly-time verifiable?

A decision problem $P$ is poly time verifiable iff there is an algorithm called verifier such that if $P(w)=$ then there is a string $c$ s.t. $(w,c)=$, if $P(w)=$ then for all strings $c$, $(w,c)=$ and V runs in $O(w^{k})$ for some constant $k$ for all inputs $w$.

# Answer
> 2 votes
No. If the problem was polynomial-time verifiable, it would be solvable in exponential time, and thus decidable; but we already know that is not decidable.

Why in exponential time? Because $V$ runs in time $|w|^k$, it can read at most $|w|^k$ bits of the input. So, it suffices to enumerate all possible strings $c$ of length at most $|w|^k$, and run $V$ on each of them. The running time will be about $2^{|w|^k}$, which is finite and thus enough to make the original problem decidable.

---
Tags: complexity-theory, np, polynomial-time
---


# Question
Title: Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true
Given $S$ of positive integers $\>$ $1$ is there some combination with **even** $SUM$ \> $2$ that is **NOT** the sum of two *primes*?

$SUM$ = 10

$S$ = $\[4,6\]$

$No$,

**Sum of Two Primes** $5 + 5 = 10$.

**Combination** $4+6=10$

It has an $O(1)$ algorithm if Goldbach is True (always output $NO$). Otherwise, it would seem to be NP-complete because it would require solving Subset-Sum.

## Question

Will a many-one-reduction from $Subset-sum$ work for this decision problem in poly-time?

# Answer
If there is a finite number of exceptions to the Goldbach conjecture then it is still solvable in linear time.

Note that there is a non-zero probability that the Goldbach conjecture is false. Heuristically, the probability for an infinite number of exceptions is zero.
> 1 votes

---
Tags: reductions, decision-problem
---


# Question
Title: checking whether turing machine passes at least k>2 states before accepting a word
$L=\\{\langle M,k\rangle \mid\exists w\in L(M) \text{ such that $M$ passes at least $k\>2$ distinct states before accepting $w$}\\}$

I try to think of reduction to prove that this language is neither RE nor coRE. How to approach this problem? Is there a hint, or intuition?

I usually check whether Rice can be used, but the question here is not about the language itself

# Answer
Clearly $L$ is acceptable (just simulate $M$ and keep track of the number of distinct states encountered during the simulation). We now show that it is not decidable.

If $L$ were decidable, you would be able to solve the Halting problem as follows: given a TM $T$ and an input $x \in \Sigma^\*$, construct a TM $M$ that ignores its input, simulates $T$ with input $x$ and, when the simulation is complete, accepts. You can further ensure that, if $M$ accepts, then it also traverses at least $3$ distinct states by just transitioning from the initial state to another (distinct) state before starting the simulation of $T$.

Now check whether $\langle M, 3 \rangle \in L$. If the answer is affirmative, then there is some $w \in \Sigma^\*$ for which $M(w)$ accepts, showing that $T(x)$ halts. If the answer is negative then $M$ never halts, showing that $T(x)$ does not halt.
> 1 votes

---
Tags: turing-machines, decision-problem
---


# Question
Title: Find all words of length $k$ in lexicographic order
Given the alphabet $\Sigma = \\{1,2,\dots, n \\}$ and a parameter $k$ how can we find all words of length $k$ over $\Sigma$ in lexicographic order?

I thought of doing this recursively, but although the task is basic it seems pretty hard to come up with a general algorithm, even when using the last word as a parameter using recursion.

Will be glad for any help

# Answer
> 1 votes
You can do it either inductively or recursively.

Inductively, you just write out the numbers from $0$ to $n^{k-1}$ in base $n$, adding $1$ to all digits.

Alternatively, you can simulate a counter in base $n$ – that would be faster.

Recursively, you can proceed as follows:

* Generate all solutions for $k-1$, and output them with prefix 1.
* Generate all solutions for $k-1$, and output them with prefix 2.
* ...
* Generate all solutions for $k-1$, and output them with prefix $n$.

Alternatively:

– Generate all solutions for $k-1$.

* For each solution $s$, output $s1, s2, \ldots, sn$.

---
Tags: algorithms
---


title: What is exactly an empty Sub-array

text:
# Question
Title: What is exactly an empty Sub-array
I read the question in Exercise **4.1-4** in Introduction To Algorithms:

> Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?

I cannot get what's an **empty sub-array**.

I came across the point that a single number can be returned if the array consists of negative elements only.

Please can anyone explain the concept of an empty sub-array? And how can we have an empty sub-array?

Even if a single element is returned it still means that sub-array is not empty. Please clear the doubt.

Edit:

To make it more clear as a question if I take an array of elements:

```
[-3,-4,-1,-8]

```

The answer would be `-1` or `0`? Please explain if why it should be `0` and how can we conclude an empty sub-array.

Thank you.

# Answer
If you have this array: $\[-2,-10,-5\]$, and the problem specifies that you should return to it the sum of the maximum subarray *whose length is at least $1$*, you will return the sum of the subarray $\[-2\]$, which is $-2$. So far so good?

Now, focus here because this is where you are most probably having trouble:

The problem is now tweaked. The problem now allows you to return to it an empty subarray, which means, you can return to it a subarray that is empty - a subarray that has no elements. Bear with me:

In mathematics, an "empty sum" is a summation where the number of terms is zero. Verify.

*Similarly,* in computer science, an "empty subarray" is a subarray in which the number of terms is zero. *This is just the definition.* It's just a subarray whose sum evaluates to zero.

Now, concerning the tweaked version of the problem, what would be better, returning to it $\[-2\]$ whose sum evaluates to $-2$, or returning the empty subarray $( \[ \ \ \ \] )$ whose sum evaluates to $0$?
> 2 votes

# Answer
A subarray of length zero is empty.

Given an array $A\[1\],\ldots,A\[n\]$, a subarray is specified by a pair of indices $i \leq j$. These correspond to the subarray $A\[i\],\ldots,A\[j\]$ of length $j-i+1$. If we also allow $j = i-1$ then we get an empty subarray of length $j-i+1 = 0$, whose sum is zero.

---

In the maximum subarray problem, we are given an array $A\[1\],\ldots,A\[n\]$, and want to find a subarray whose sum is maximal. If we don't allow empty subarrays, this means that we are looking for the maximum value of $$ A\[i\] + \cdots + A\[j\], $$ where $1 \leq i \leq j \leq n$. If we are allowing empty subarrays, then we take the maximum of that with $0$, which is the sum of the empty subarray.

This only makes a difference if all entries of the array are negative. The maximum sum of a non-empty subarray is in this case the maximal element $A\[i\]$, which is the sum of the subarray $A\[i\]$ of length $1$. The empty subarray, however, has a larger sum: $0$. Therefore if the empty subarray is not allowed, the answer should be $\max\_i A\[i\]$, and if it is allowed, the answer should be $0$.
> 2 votes

---
Tags: algorithms, maximum-subarray
---


# Question
Title: Confusion in Turings proof of the undecidability of the Entscheidungsproblem
I was reading Turing's paper on computable numbers and the Entscheidungsproblem. There is this part of Section 9, Part II that I cannot quite seem to understand. He says:

It is pretty straight forward until the part where he introduces $\mathfrak{U}$. So $\mathfrak{U}$, he says, includes the Peano axioms; but what else does it include? I guess it includes the axioms for $G(x)$ as well, because only then would $\mathfrak{U}$ be able to "define" the sequence $\alpha$ that is being computed by $G(x)$. I am taking the word "define" here in its usual sense, but Turing explains what he means by "$\mathfrak{U}$ defining $\alpha$" as:

So for $\mathfrak{U}$ to define $\alpha$, $-\mathfrak{U}$ must *not* be provable? I am not sure why that is required? Because by restricting that $-\mathfrak{U}$ must not be provable we are saying that $\mathfrak{U}$ must *not* be refutable, which means that the sequence $\alpha$ *cannot* be all 0's (or so I think). But why would we want $\alpha$ to not be all 0's?

I am also confused about the two formulas ($A\_n$ and $B\_n$) he has written above. I am not sure why if has included the $F^{(n)}$ part. If $x$ satisfies the Peano axioms and the axioms of $G(x)$, then $U$ being a conjection of all these axioms is given to be **TRUE**, and if $x$ does not satisfy these axioms then $\mathfrak{U}$ is obviously **FALSE**. So, just based on $\mathfrak{U}$ we can tell whether $A\_n$ is **TRUE** or $B\_n$. So what is the point of $F^{(n)}$ here? I think the following set of implications say pretty much the same thing as what Turing has?

Sorry if I am overlooking something here.

**Edit 1:**

Here are the footnotes:

# Answer
The transliteration of the passage into modern langauge would go as follows.

We extend the language of first-order Peano arithmetic with a unary predicate $G$ (and no axioms for $G$). For a number $n \in \mathbb{N}$, let $\overline{n}$ be the numeral $$\underbrace{S(S(\cdots S}\_{n}(0)))$$ where $S$ is the successor symbol. For example, $\overline{3} = S(S(S(0))$.

Consider a formula $\mathfrak{U}(x)$ written in this language, whose only free variable is $x$ such that, for every $n \in \mathbb{N}$:

1. Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow G(\overline{n})$, or
2. Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow \lnot G(\overline{n})$.
3. Peano axioms do *not* prove $\lnot \mathfrak{U}(\overline{n})$.

Define $\alpha : \mathbb{N} \to \\{0,1\\}$ by $$\alpha(n) = \begin{cases} 1 & \text{if Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow G(\overline{n})$},\\ 0 & \text{if Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow \lnot G(\overline{n})$.} \end{cases} $$ We say that **$\mathfrak{U}$ defines the sequence $\alpha$**.

Intuitively, we think of $G(x)$ as stating "the $x$-th digit of $\alpha$ is $1$", and of $\lnot G(x)$ as stating "the $x$-th digits of $\alpha$ is $0$".

The first and second condition on $\mathfrak{U}$ ensure that $\mathfrak{U}$ always assigns $\alpha(n)$ the value $0$ or the value $1$.

The third condition ensures that $\mathfrak{U}$ never assigns *both* $0$ and $1$ to $\alpha(n)$ (because it follows from the first two conditions that $\lnot \mathfrak{U}(\overline{n})$ is equiprovable with $G(\overline{n}) \land \lnot G(\overline{n})$).

**Example:** The formula $G(x)$ defines the sequence $1, 1, 1, 1, 1, \ldots$.

**Example:** The formula $G(S(x))$ does not define a sequence because $G(S(0)))$ does not imply $G(0)$ and it does not imply $\lnot G(0)$. (Remember that $G$ is a primitive symbol and that we have no axioms about it.)

**Example:** The formula $G(0) \land \forall x \\,.\\, \lnot G(S(x))$ defines the sequence $1, 0, 0, 0, 0, \ldots$

**Example:** The formula $x \neq 0 \land \Rightarrow G(x)$ does not define the sequence because Peano axioms prove $\lnot (0 \neq 0 \land G(0)$, thus the third condition is violated. If we tried to use this formula to define a sequence, it would assign $0$ and $1$ to $\alpha(0)$ (and it would assign $1$ to all other terms of $\alpha$).

**Example:** The formula $G(0) \land \lnot G(S(0)) \land \forall x . G(S(S(x)))$ defines the sequence $1, 0, 1, 1, 1, 1, \ldots$

**Example:** The formula $$((\exists y . x = 2 \cdot y) \Rightarrow G(x)) \land ((\exists y . x = S(2 \cdot y)) \Rightarrow \lnot G(x)) $$ defines the sequence $0, 1, 0, 1, 0, 1, \ldots$
> 6 votes

---
Tags: turing-machines, turing-completeness
---


# Question
Title: Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$
I'm having a small issue with wikipedia's proof that $RP \subseteq NP$:

> An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic Turing machines where the machine accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept. NP on the other hand, needs only one accepting path, which could constitute an exponentially small fraction of the paths. This characterization makes the fact that RP is a subset of NP obvious.

My problem lies in the following statement: "...accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept"

My question is: for a language $L \in NP$, wouldn't it only need one computation path for the non-deterministic TM to accept? Since, if $x \in L$, $P\[T(x) accepts\] \>= 1/2$ with $T$ being the Turing machine that decides $L$.

# Answer
> 3 votes
Fix some $L\subseteq RP$. Then:

1. if $x\in L$ then $P\_y\[T(x,y)\text{ accepts}\]\ge {1\over2}$, therefore **exists** some $y$ where $T(x,y)$ accepts.
2. if $x\notin L$ then $P\_y\[T(x,y)\text{ accepts}\]=0$, therefore **for every** $y$ we have $T(x,y)$ rejects.

Thus, by definition of $NP$, $L\in NP$.

As you can see from this proof, you are correct: $NP$ requires **one path** while $RP$ requires **at least half of the paths**

---
Tags: complexity-theory, reductions, np, complexity-classes, randomness
---


# Question
Title: Augmenting AVL tree to calculate sum of subtree
Suggest a way to augment an AVL tree to support a $O(\log n)$ implementation of the function `calculateSum(key)`, which receives a key of a node and returns the sum of its subtree.

I implemented it this way:

```
sumSubtree(node):
    if node != null:
        return sumSubtree(node.left) + sumSubtree(node.right) + node.key
    return 0

calculateSum(key):
    node = Search(key) // assuming I have a search function
    return sumSubtree(node)

```

which solves it in $O(\log n)$.

But I read it is possible to maintain the sum during insertion and deletion. And augment an AVL tree this way.

Which solution would be better? Mine, or the other method? Does it matter?

# Answer
> 0 votes
Your solution is traversing the whole subtree on each call to `subSubtree` so it is actually $O(|T|) \neq O(\log n)$ where $|T|$ is the length of the subtree. If I query the root of the tree it will go over every node, so complexity is $O(n)$.

If you keep the sum of the subtree while modifying it (insertions/deletions) then the pseudo-code will look like:

```
calculateSum(key):
    node = Search(key) // assuming I have a search function in O(log n)
    return node->size

```

Search can be implemented in $O(\log n)$ and getting the size is $O(1)$ since it is stored on the node itself, hence the overall complexity will be $O(\log n)$.

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


# Question
Title: Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items
Assume for the regular knapsack problem we have additional information - maximal weight of every item - lets denote it as P. Using this information, I want to solve the problem using dynamic programming in $O(n^2P)$. Anyone have an idea how to solve it?

# Answer
> 1 votes
If $W \ge n \cdot P$ you can add all elements in the knapsack.

Otherwise $W \< n \cdot P$ in which case any algorithm with complexity $O(n W)$ will also have complexity $O(n \cdot (nP)) = O(n^2P)$. In particular the pseudo-polynomial dynamic programming solution described in Wikipedia works in $O(n W)$.

---
Tags: graphs, dynamic-programming
---


title: Confusion about the Hiring Problem

text:
# Question
Title: Confusion about the Hiring Problem
I'm confused about where the probability from the hiring problem comes from.

For background:

> We interview one person everyday who has a quality characteristic, x, from 0 to 1(distributed uniformly). We interview for n days. If on the $i^{th}$ day, person i is more qualified then all the **previous** candidates, then we hire that person. Find the expected number of people we hire.

We can proceed to solve the problem using linearity of expectation and the method of indicator random variables.

Let X be the number of people we hire. $$X = X\_1 + X\_2 + X\_3 + ... + X\_n$$ where $X\_i = 1$ if we hire the with person and $X\_i = 0$ if we don't. According to online resources, the probability that we hire the with person is $\frac{1}{i}$ since each person is equally likely to be the highest so far.

However, this doesn't make sense to me. Why doesn't the probability that we hire the $i^{th}$ person depend on the quality characteristic we've seen so far?

Take, for example, the second person: Shouldn't the $(2^{nd} \text{person hired}) =1 - n\_1$ where n\_1 is the quality characteristic of the first person?

If we use what online resources say then $P (2^{nd} \text{person hired}) = \frac{1}{2}$. But what if person one had a quality characteristic of .9, then $P(2^{nd} \text{ person hired}) = .1$ and not half.

Can someone tell me where my logic is wrong?

# Answer
> 1 votes
Let us denote by $x\_1,\ldots,x\_n$ the qualities of the $n$ persons; so the $x\_i$ are iid random variables distributed uniformly over $\[0,1\]$.

If you know $x\_1,\ldots,x\_i$, then $X\_i$ becomes deterministic. For example, if $x\_1 = 0.3$ and $x\_2 = 0.5$ then $X\_2 = 1$, whereas if $x\_1 = x\_2 = 0.4$ and $x\_3 = 0.1$ then $X\_3 = 0$. If you know only some of $x\_1,\ldots,x\_i$, then you can calculate the distribution of $X\_i$, as your example demonstrates.

None of this is needed to calculate $\mathbb{E}\[X\]$, however. Using linearity of expectation, we know that $$ \mathbb{E}\[X\] = \sum\_{i=1}^n \mathbb{E}\[X\_i\] = \sum\_{i=1}^n \Pr\[X\_i = 1\]. $$ In other words, in order to calculate the expected number of people hired, all we need to do is to calculate the probability that $X\_i = 1$. This probability is $1/i$. You're right that the probability changes if we know more about the $x\_j$, but so what? We are not interested in calculating $\mathbb{E}\[X\]$ given partial knowledge of the $x\_j$. Instead, we want to calculate the expected value of $X$ when $x\_1,\ldots,x\_n$ are chosen uniformly at random from $\[0,1\]$, independently. This is the relevant distribution for calculating $\Pr\[X\_i = 1\]$.

What might be throwing you off is the trick of using linearity of expectation. It allows us to treat the random variables $X\_i$ completely independently, although the variables themselves are certainly dependent.

---
Tags: algorithms, probability-theory, discrete-mathematics, randomized-algorithms, probabilistic-algorithms
---


# Question
Title: Why are the two random variables independent in the analysis of Randomized Selection algorithm in CLRS?
In section 9.2 of CLRS (*Introduction to Algorithms; page 185 in the 2nd edition and page 215 in the 3rd edition*), a randomized selection algorithm is presented.

For its analysis, $T(n)$ is a random variable denoting the time required on an input array $A\[p \cdots r\]$ of $n$ elements and $X\_k$ is an indicator random variable $X\_k = I \\{ \text{the subarray } A\[p \cdots q\] \text{ has exactly } k \text{ elements (due to the pivot)} \\}$.

It has been claimed that $X\_k$ and $T(\max(k-1, n-k))$ are independent (page 187 in the 2nd edition and page 218 in the 3rd edition). However, I find it quite counter-intuitive to understand. How to verify it?

# Answer
> 2 votes
The two random variables $X\_k$ and $T(\max(k-1, n-k))$ are independent because in each recursive call to RANDOMIZED-SELECT() we invoke RANDOMIZED-PARTITION(), a pivot is randomly selected, and the choice of the pivot in one recursive call is *independent* from the choice of the pivot in another recursive call. Remember that in the analysis we assume that the elements are distinct, so that each element in a particular subarray has the same probability of being selected as the pivot. Moreover, simply stated, the value of $\max(k-1,n-k)$ does not depend on $X\_k$: it is the same independently of $X\_k$ being equal to zero or one.

# Answer
> 1 votes
Apparently it seems that "$X\_k$ and $T(\max(k-1,n-k)$ are independent" is counter-intuitive, as at glimpse it seems that the value of $X\_k$ depends on $k$ and so does $T(\max(k-1,n-k)$. So to clarify the situation we much look at the case and definition more closely.

Now as per the definition, $X\_k$ is used to reflect the randomness of the algorithm in the recurrence relation of its time complexity. **A deeper look at the definition of $X\_k$ says that it depends on the value of the index of the pivot which is chosen in a particular call to the RANDOMIZED-PARTITION.** As only one index of the array is selected as the pivot in a particular call to RANDOMIZED-PARTITION $X\_k$ can have the value $1$ only for that particular pivot index $k$ and all other indices we have $X\_k=0$ and the summation on the RHS of the recurrence reduces to only one term.

$$\sum\_{k=1}^{n} X\_k.T(\max(k-1,n-k))$$

$$=X\_1.T(\max(1-1,n-1))+X\_2.T(\max(2-1,n-2))+X\_3.T(\max(3-1,n-3))+\ldots+X\_n.T(\max(n-1,n-n)) \tag 1$$

Now suppose if RANDOMIZED-PARTITION returns $2$ we have,

$$=0.T(\max(1-1,n-1))+1.T(\max(2-1,n-2))+0.T(\max(3-1,n-3))+\ldots+0.T(\max(n-1,n-n))$$

Or if RANDOMIZED-PARTITION returns $n$ we have,

$$=0.T(\max(1-1,n-1))+0.T(\max(2-1,n-2))+0.T(\max(3-1,n-3))+\ldots+1.T(\max(n-1,n-n))$$

Note that in $(1)$ whatever be the value of $X\_k$ the value $T(\max(k-1,n-k))$ does not change, this is so because of the following,

Thought it seems that $X\_k$ depends on the summation variable $k$ but it is not the complete truth.

A more closer look into the definition of this indicator random-variable shows that $X\_k$ depends on whether a particular value of the summation variable is choosen as the pivot index by the RANDOMIZED-PARTITION. So if in a call RANDOMIZED-PARTITION selects the pivot index as say $j$ then for $k=j$ we have $X\_j=1$ and zero for all other $X\_{k\neq j}$. So $X\_k$ depend on the RANDOMIZED-PARTITION.

On the other hand $T(\max(k-1,n-k))$ is a random variable (as the text defines) but it has as its parameter $\max(k-1,n-k)$ which in turn depends only on the summation variable and no other hidden conditions.

From our above two claims we can say that $X\_k$ and $T(\max(k-1,n-k)$ are independent.

---
Tags: algorithm-analysis, randomized-algorithms
---


# Question
Title: 'Half-Close' figure of Data Communications and Networking, 5/e
In the Figure 24.13 of Data Communications and Networking, 5/e the first **ACK** message from the server holds `y-1` in it's *Sequence no.* field. Note that the first **FIN** message from the client message had `y` in it's *Acknowledgement no.* field. So shouldn't the first **ACK** message from the server be holding `y` in it's *Sequence no.* field instead of holding `y-1`? Is the diagram faulty or is there a reason behind it?

# Answer
> 0 votes
The `FIN` segment consumes 1 sequence number as it does not carry data. `ACK` does not consume a sequence number. The `FIN` segment is sent by the client process. The server process receives a `FIN` segment but **does not send a `FIN` segment as the connection is not closed**, since it is a half-close process. Server process send only an `ACK` segment to acknowledge receipt of `FIN` segment from the client. Hence, the sequence number decreases by 1 and becomes $y-1$.

Contrast this with the Three way handshaking, where the sequence number is $y$ because in that process, the server sends a `ACK` segment as it acknowledges receipt of `FIN` segment from the client *and* sends a FIN segment as it terminates the connection.

---
Tags: computer-networks, communication-protocols, tcp
---


# Question
Title: Intuition of lower bound for finding the minimum of $n$ (distinct) elements is $n-1$ as dealt with in CLRS
I was going through the text Introduction to Algorithms by Cormen et. al. where there was a discussion regarding the fact that finding the minimum of a set of $n$ (distinct) elements with $n-1$ comparisons is optimal as we cannot do better than it, which means that we need to show that running time of algorithm which finds the minimum of a set of $n$ elements is $\Omega(n)$.

This is what the text says to justify the lower bound.

> We can obtain a lower bound of $n - 1$ comparisons for the problem of determining the minimum. Think of any algorithm that determines the minimum as a tournament among the elements. Each comparison is a match in the tournament in which the smaller of the two elements wins. Observing that every element except the winner must lose at least one match, we conclude that $n-1$ comparisons are necessary to determine the minimum.

Now I could make the thing out in my own way as:

What I have done is a top down comparison, but the authors by their words *"Observing that every element except the winner must lose at least one match, we conclude that $n-1$ comparisons are necessary to determine the minimum."* seems they are pointing to some bottom up approach which unfortunately I cannot make out.

How,

"That every element except the winner must lose at least one match" $\implies$ "$n-1$ comparisons are necessary to determine the minimum".

# Answer
> 1 votes
Every match has exactly one winner and one loser. If every element except the winner must lose at least one match, there must be at least $n-1$ matches, as otherwise there would be a match with two losers. So, at least $n-1$ matches are nessecary to determine a winner, i.e. $n-1$ comparisons are nessecary to determine the minimum.

---

The explanation given in the book is valid, but I personally prefer another approach. (which does require some elementary graph theory) Suppose you draw the graph with the elements as nodes and you draw an edge for each pair of elements that your algorithm compares. Note that it is impossible to know which of a pair of elements is smaller if there is no path between them in this graph. So, if we have determined the minimum, this graph must connected. Any connected graph on $n$ nodes has at least $n-1$ edges, so there must have been $n-1$ comparisons.

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


# Question
Title: What is the computational complexity of "real-life" regular expressions?
Regular expressions in the sense as equivalent to regular (Chomsky type 3) languages know concatenation `xy`, alternation `(x|y)`, and the Kleenee star `x*`.

"Real-life" regular expressions as used in programming usually have a lot more operations available; amongst others, quantification `x{n}`, negation `[^x]`, positive and negative lookahead `x(?=y)`, or back-reference `\n`.

There is a famous post on SO stating that regular expressions can not be used to parse HTML for the reason that HTML is not a regular language.

My question is: Is this accurate? **Do "real-life" regular expressions, say the selection defined in the Java docs, really have the same expressive power as regular expressions as understood in formal language theory; or do the additional constructs, although possibly not strong enough to capture HTML and the like, put common regular expressions further up on the Chomsky scale than just Type 3 languages?**

I would imagine the proof of the computational equality of the two would amount to showing that each operation available for the common regexp is just syntactic sugar and can be expressed by means of the 3 basic operations (concatenation, alternation, Kleene start) alone; but I am finding it hard to see how one would e.g. simulate back-reference with classic regexes alone.

# Answer
The following extended regular expression matches the language $\\{ ww : w \in \Sigma^\* \\}$:

$$ \texttt{^\\\(.\*\\\)\\1\\\\$} $$

This language is neither regular nor context-free.

Matching using extended regular expressions is NP-complete; see for example this paper, which discusses efficient algorithms in some special cases.
> 5 votes

---
Tags: formal-languages, regular-expressions, chomsky-hierarchy
---


title: What can this circuit be useful for?

text:
# Question
Title: What can this circuit be useful for?
I have calculated the boolean functions for $r$ and $f$:

$f = \overline{s\_1} \cdot s\_0 + s\_1 \cdot \overline{s\_0}$.

$r = \overline{s\_0 \cdot s\_1 \cdot s\_2 \cdot s\_3}$.

Do you have an idea what an application for this circuit can be? I don't know where we would use it.

# Answer
> 1 votes
Good Question. It looks like some kind of ripple counter. It repeats after 15 steps. Values (consider the outputs to be 8,4,2,1) as 8,4,2,9,12,6,11,5,10,13,14,15,7,3,1.

Zero only for one step after reset, not repeated.

---
Tags: circuits, digital-circuits
---


# Question
Title: Why minimum vertex cover problem is in NP
I am referring to the definition of the **minimum vertex cover** problem from the book *Approximation Algorithms* by Vijay V. Vazirani (page 23):

> Is the size of the minimum vertex cover in $G$ at most $k$?

and right after this definition, the author states that this problem is in **NP**.

**My question**: What would be a *yes certificate*?

Indeed, our non-deterministic algorithm could guess a subset of vertices, denoted by $V'$, and we can verify if $V'$ is a vertex cover of some cardinality in polynomial time, but how could we possibly show that $V'$ is *minimum* in polynomial time?

# Answer
You don't have to verify that $V'$ is minimum. The decision version of Vertex Cover (which you have quoted in your question) only asks you to decide whether there is a vertex cover of size at most $k$.

To verify that $V'$ is a valid yes-certificate for an instance $\langle G=(V,E), k \rangle$ you just check that:

* $V' \subseteq V$,
* $|V'| \le k$, and
* $\forall (u,v) \in E, \\{u,v\\} \cap V' \neq \emptyset$.
> 2 votes

---
Tags: complexity-theory, graphs, time-complexity, np-complete, decision-problem
---


# Question
Title: For selection in worst-case linear time ambiguity in consideration of $n$ for which $T(n) =O(1)$ and $T(n)\leq cn$
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the recurrence relation for analyzing the time complexity of the linear SELECT algorithm and I felt that few things probably mismatch with respect to the range of $n$, the input size for which $T(n)$ is assumes $O(1)$ and $cn$ in the substitution method.

The details of the text are as follows:

---

We can now develop a recurrence for the worst-case running time $T(n)$ of the algorithm SELECT. Steps 1, 2, and 4 take $O(n)$ time. (Step 2 consists of $O(n)$ calls of insertion sort on sets of size $O(1)$ Step 3 takes time $T(\lceil n/5 \rceil)$, and step 5 takes time at most $T(7n/10+ 6)$, assuming that T is monotonically increasing. ***We make the assumption, which seems unmotivated at ﬁrst, that any input of fewer than $140$ elements requires $O(1)$ time; the origin of the magic constant $140$ will be clear shortly.***$^\dagger$ We can therefore obtain the recurrence

$$T(n) \leq \begin{cases} O(1)&\quad\text{if $n\<140$ $^\ddagger$} \\ T(\lceil n/5 \rceil)+T(7n/10+ 6)+O(n)&\quad\text{if $n \geq 140$ $^\\|$}\\ \end{cases}$$

We show that the running time is linear by substitution. More speciﬁcally, we will show that $T(n)\leq cn$ for some suitably large constant $c$ and ***all $n \> 0$***. We begin by assuming that $T(n)\leq cn$ for some suitably large constant $c$ and ***all $n \< 140$*** $^{\dagger\dagger}$; this assumption holds if $c$ is large enough. We also pick a constant a such that the function described by the $O(n)$ term above (which describes the non-recursive component of the running time of the algorithm) is bounded above by an for all $n \> 0$. Substituting this inductive hypothesis into the right-hand side of the recurrence

$$T(n) \leq c\lceil n/5 \rceil + c(7n/10+6) +an$$

$$\leq cn/5 + c + 7cn/10 + 6c +an$$

$$= 9cn/10+7c+an$$

$$= cn+(-cn/10+7c+an).$$

which is at most $cn$ if

$$-cn/10 + 7c + an \leq 0.\tag 1$$

$$\iff c\geq 10a(n/(n-70)) \quad\text{when n\>70} $$

Because we assume that $n\geq 140$ $^{\ddagger\ddagger}$ we have $n/(n-70)\leq 2$ and so choosing $c\geq 20a$ will satisfy the inequality $(1)$

---

$$ \dagger \quad \text{The statement here complies with the $\ddagger$ in the recurrence relation} $$

$$ \dagger\dagger \quad \text{The statement here does not comply with the $\\|$ in the recurrence relation} $$

$$ \ddagger\ddagger \quad \text{The statement here does comply with the $\\|$ in the recurrence relation} $$

---

I could not quite understand this discrepancy, however I did not include the entire algorithm (available in CLRS Section $9.3$) but if incase it is needed please say then I shall include it as well.

# Answer
It seems that $\dagger\dagger$ is consistent with $\\|$. You just need to pick a constant $c$ that is larger than or equal to the constant $\gamma$ hidden in the $O(1)$ notation in the definition of $T(n)$ for $n \< 140$ (i.e., the line marked with $\ddagger$).

Then, for any $n \in \\{1, \dots, 139\\}$, you have $T(n) \le \gamma \le c \le cn$, as desired.
> 2 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, recurrence-relation, check-my-answer
---


title: Contiguous Subarray Max

text:
# Question
Title: Contiguous Subarray Max
I'm trying to solve the contiguous subarray problem on CodeSignal & I came up with the following solution which is based off of Kadane's Algorithm. *My implementation passed the given test data set however upon submission, it failed.* There's no reason given on CodeSignal & I can't look at it since I just started doing it & have less coins.

*I can't figure out why my solution is failing but the solution based on online pseudo code works*, even though my solution passed the preliminary tests. I think it might have to do with integer overflow or some other reason *that's why I've come here to seek help from experts.*

My implementation:

```
 public int findConsecutiveSubarray(int nums[]) {
    int currentSum = 0;
    int max =Integer.MIN_VALUE;;

    int i=0;
    while(i < nums.length) {
        currentSum += nums[i];

        if(max < currentSum)
            max = currentSum;

        if(max < nums[i]) {
            max = nums[i];
            currentSum = nums[i];
        }

        i++;
    }
    System.out.println("maxSum : "+ max);
    return max;
}

```

Solution based on online:

```
int arrayMaxConsecutiveSum2(int[] nums) {
        int currentMax = 0;
        int globalMax = 0;

        globalMax = currentMax = nums[0];

        for(int i=1; i<nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            globalMax = Math.max(globalMax, currentMax);
        }

    return globalMax;
}

```

# Answer
The issue is that you might not enter the second "if" when the current sum is smaller than `nums[i]`. Imagine, e.g., that at the beginning of the iteration you have `currentSum=-5`, `max=100`, `nums[i]=10`. At the end of the iteration you have `currentSum=5` and `max=100`, yet the desired state is `currentSum=10`, `max=100`.

A corresponding instance where your algorithm fails is: `100, -105, 10, 95`.

To fix this, the condition of the second "if" should be `currentSum < nums[i]`.

Notice that, once you change this condition, you'll also have to revise other parts of your code accordingly: you can no longer unconditionally assign `max` to `nums[i]` in the body of the second "if" statement. This can be easily fixed by removing that assignment and swapping the order of your two ifs.

```
[...]
        if(currentSum < nums[i])
            currentSum = nums[i];

        if(max < currentSum)
            max = currentSum;
[...]

```
> 1 votes

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


# Question
Title: Can choice function in SHA algorithm be used in a simplied way?
While going through the official documentation SHA algorithms from NIST here.

There is a choice and Majority function used. Maj(,,)=(∧)⊕(∧)⊕(∧)
Ch(,,)=(∧)⊕(¬∧)

Can I use Ch (or Maj) function in a simplified version?

eg:

(x^y)⊕(¬∧)
=(x^y)^ ¬(¬∧) + ¬(x^y)^ (¬∧)
=(x^y)^(x + ¬z) + (¬x + ¬y)^ (¬∧) can be further simplified as

(x^y) + (¬x ^z)

can above simplified version be used ??

# Answer
I'm not familiar with the details of SHA but if we interpret $0$ as false and $1$ as true, then $a+b$ and $a \oplus b$ only differ when $a=b=1$.

In your specific case $(x \wedge y)$ and $(\neg x \wedge z)$ cannot both be true. This is easy to see since you would need to simultaneously have $x=1$ and $x=0$.

It follows that $(x \wedge y) \oplus (\neg x \wedge z)$ and $(x \wedge y) + (\neg x \wedge z)$ are equivalent. The same holds true if $x$, $y$, and $z$ are binary numbers and $\neg$, $\wedge$, and $\oplus$ are interpreted as bitwise operators.

This equality does **not** hold for the case of $\text{Maj}(x,y,z)$, as you can check by setting $x=y=z=1$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Sets in Mathematics are immutable but in Computer Science sets are mutable and called "Dynamic Sets" - truth of the statement
While reading the classic text Introduction to Algorithms by Cormen et. al. I came across the following claim:

> Sets are as fundamental to computer science as they are to mathematics. Whereas mathematical sets are unchanging, the sets manipulated by algorithms can grow, shrink, or otherwise change over time. We call such sets ***dynamic***.

I felt a bit odd after reading the statement that "set" in Mathematics and in CS are different from the mutable point of view. Now in Mathematics what we deal with are theoretical aspect of things and as such "set" is a theoretical concept and so it is in Theoretical CS. If it is immutable in mathematics then so it is in CS. Mathematics and Theoretical CS are interlinked. So given a graph algorithm which say finds the minimum shortest path between a pair of vertices , we can't say whether it belongs to Mathematics or CS.

Often in algorithms we write statements as :

$$S = S \cup \\{a\\} \quad \text{view $1$}$$

Which seems to sort of change our set $S$, but if we look it in this way:

$$S'= S \cup \\{a\\} \quad \text{view $2$}$$

$$S=S'$$

So in the second situation we are not modifying our actual set $S$ we are forming a new set $S'$ with $S$ augmented with $a$ and then after that we are making the variable $S$ refer to $S'$.

What I feel is that the concept of the set being mutable or immutable is solely dependent on the data-structure of representation of the abstract concept of "sets" and since in data-structure the two steps in view $2$ are combined and implemented, so they are called *dynamic sets*.

In short I feel that *Dynamic Sets* are data-structure implementation of sets and not the abstract sets.

# Answer
> 2 votes
Set are at a higher level of abstraction than algorithms. You can certainly analyze algorithms at that level of abstraction but that's not the usual level of abstraction for discussing algorithms, instead you'd refer to data structures such as stacks, vectors, lists, linked lists etc.

Sets are instead used in formal modeling contexts (Z,Coq,Agda,F-Star) to describe specifications but not algorithms.

They're also used do describe algorithms in functional programming (see e.g. Purely Functional Data Structures by Chris Okasaki ) but that is not very common in literature as most algorithms are described in terms of ephemeral data structures.

To answer your question, sets are the same both in Mathematics and CS, they're immutable. Dynamic sets is a data structure loosely related to sets.

The author is not saying that sets are different in CS than in Mathematics. He's saying that the data structures, as commonly described in algorithms are mutable. CS is much more than algorithms and data structures.

---
Tags: sets, mathematical-foundations, definitions
---


# Question
Title: What is the goal of studying all those NP-complete problems?
So i'm currently reading a lot of things about graph NP-complete problems, and it seems that the goal of a lot of researchers is to find new results about their complexity, results like "independent set is 1.593 approximable for graphs which doesn't contains K4 K5 P3 as a minor" (this is probably a wrong result i just invented something which looks like a result we could find in a paper), approximation algorithms, parameterized complexity etc ...

But i'm wondering : what really is the goal to study independent set, vertex cover, hamiltonian circuit etc ... ? Do they have real case application ? Is there any software that uses independent set algorithms ?

Or is it only for the theory ? To discover something new in the P vs NP problems ?

To sum up : are NP-complete problems (and i'm particularly interested in NP-complete graph problems) useful in the reality ?

PS : sorry if the title may seem offensive, it is not, i know a lot of searchers study things which does not have much applications in reality, i want to know if it is the case for np-complete problems

# Answer
No one are offended by that question, and it's an important question to ask.

When working in graph theory, we don't believe that proving hardness results for independent set on $\\{K\_4, K\_5, P\_3\\}$-minor-free graphs are "important". However, it is interesting to see *why* a certain forbidden minor puts a problem from being, e.g. polynomial time solvable, to NP-complete. It is then important that *that* is the focus.

Here is an interesting problem:

> Does edge deletion to claw-free graphs admit a polynomial kernel?

Why is it interesting? Because we know almost everything else about kernels and edge deletion to $H$-free graphs. This one is interesting because it is notoriously hard. And hopefully, once this is solved, we will understand more about the interplay between $H$-free graphs, edge deletion, and polynomial kernels.

But I want to also mention that, yes, there are indeed applications that use algorithms for independent set, vertex cover, travelling salesman, etc. See for example Dependency hell is NP-complete.

---

Fast forward to *industry*. After quitting academia and joining industry as a developer, I have more than once been able to tell people that what they are working on is NP-complete, and to provide insight into a problem that I got from studying these problems in a theoretic setting.

I have written and published my share of "unusable" algorithms, but it's not expected that people can take algorithms and plug-and-play them into their system. What they *can* take is the insight we provide in structures, heuristics, as well as hardness. Sometimes a problem is only hard on graphs that have large grids as minors, and if you suddenly see that your data is "tree-like", then you might have some tricks to share with your future industry-colleagues.
> 5 votes

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


# Question
Title: reduction of independence problem and cluster problem
independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them.

cluster problem is: there is a simple and undirected graph, we are looking for the maximum number of the vertex in which there are proximity every two vertexes ( there is an edge between any two vertexes)

how can I reduct independent problem to cluster problem and vise versa?

# Answer
If i understand your question correctly, given $G$, build a graph $G'$ where $V(G)=V(G')$ and for every $v,u\in V(G)$, $(v,u)\in E(G')\iff(v,u)\notin E(G)$
> 1 votes

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


# Question
Title: Regular of language of all words of length 3
Consider the language $$L = \\{ x \in \\{0,1\\}^\* \mid |x| = 3 \\}.$$

I think the above language is regular. A DFA can be used to determine the above language.

> Am I correct? Is the above language regular?

If this language $L$ is regular, then it should satisfy the pumping lemma. Then there exist $w = xyz$, where $xy^nz \in L$ for all $n \ge 0$.

But on the other hand, if we pump more letters then the resulting string will not be in the language. The language $L$ only contains words of length 3.

The pumping lemma states that for every regular language there exists an integer $p$, such that string $w$ of length at least $p$ can be written as $w = xyz$ and $y$ can be pumped.

Here are my doubts.

1. Is this language $L$ regular?
2. If so, does it satisfy the pumping lemma?
3. The pumping lemma states that every regular language has a pumping length $p \ge 1$. Does this language not have one?

# Answer
> 1 votes
Every finite language is regular. If $L$ is a finite language and $p$ is larger than the length of all words in $L$, then $L$ satisfies the pumping lemma with the constant $p$. Indeed, every word in $L$ of length at least $p$ can be pumped (vacuously).

# Answer
> 0 votes
Take pumping length = 4. All strings in the language with length greater than the pumping length must meet some condition. Since there are no strings in the language with length \> 4, all these strings, all zero of them, meet any condition, and therefore the language is regular.

That’s true for any finite language where you can just take the pumping length longer than the longest string in the language.

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


# Question
Title: Complexity of class finding selection of entries in matrix
Suppose I have a matrix with entries either $x$ or $y$, where the number of rows = number of columns = $n$. If I want to select/circle $n$ entries such that for each row, only exactly one is circled, for each column, also exactly one is circled, and such that all entries circled are only $x$ (if such a circling of entries exists), what complexity class does this belong to? Thanks!

# Answer
> 1 votes
Let $U$ be the set of rows in the given matrix and $V$ the set of columns. For each $x$ at row $i$ and column $j$, add an edge between row $i$ and column $j$. You will have an (unweighted) bipartite graph $G=(U,V, E)$. The problem is to find a perfect matching, which is basically the same as find the maximum matching of $G$.

There are various algorithms that compute the maximum cardinality matching. For example, The Hopcroft–Karp algorithm runs in $O(\max(|E|\sqrt {|V|}, |V|^2)$.

So, we can say that the complexity class of the problem in the question is in $O(n^{2.5})$ since $|E|\le n^2$ and $|V|= 2n$.

---
Tags: time-complexity, complexity-classes, matrices
---


# Question
Title: Uniform Hashing. Understanding space occupancy and choice of functions
I'm having troubles understanding two things from some notes about Uniform Hashing. Here's the copy-pasted part of the notes:

> Let us first argue by a counting argument why the uniformity property, we required to good hash functions, is computationally hard to guarantee. Recall that we are interested in hash functions which map keys in $U$ to integers in $\\{0, 1, ..., m-1\\}$. The total number of such hash functions is $m^{|U|}$, given that each key among the $|U|$ ones can be mapped into $m$ slots of the hash table. **In order to guarantee uniform distribution of the keys and independence among them, our hash function should be anyone of those ones.** But, in this case, its representation would need $\Omega(log\_2 m^{|U|}) = \Omega(|U| log\_2 m)$ bits, which is really too much in terms of space occupancy and in the terms of computing time (i.e. it would take at least $\Omega(\frac{|U|log\_2 m}{log\_2 |U|})$ time to just read the hash encoding).

The part I put in bold is the first thing is confusing me.

*Why the function should be any one of those? Shouldn't you avoid a good part of them, like the ones sending every element from the universe $U$ into the same number and thus not distributing the elements?*

The second thing is the last "$\Omega$". *Why would it take $\Omega(\frac{|U|log\_2 m}{log\_2 |U|})$ time just to read the hash encoding?*

The numerator is the number of bits needed to index every hash function in the space of such functions, the denominator is the size in bits of a key. Why this ratio gives a lower bound on the time needed to read the encoding? And what hash encoding?

# Answer
> 1 votes
Suppose that we sample a hash function $h$ at random from a collection $\mathcal{H}\subseteq \[m\]^U$ (we denote by $\[m\]$ the set $\\{0,1,...,m-1\\}$). The best possible thing we can require from this choice is that $\left(h(x\_1),h(x\_2),....,h(x\_{|u|})\right)$ are jointly uniformly distributed over $\[m\]^U$, where $U=\\{x\_1,...,x\_{|U|}\\}$ (this in turn implies independence). Fix some $h\_0\in \[m\]^U$, then under the previous requirement we have:

$\Pr\limits\_{h\sim\mathcal{H}}\[h=h\_0\]=\Pr\limits\_{h\sim\mathcal{H}}\left\[h(x\_1)=h\_0(x\_1)\land...\land h(x\_{|U|})=h\_0(x\_{|U|})\right\]=\frac{1}{m^{|U|}}$.

It follows that $h$ is uniformly distributed over all possible functions in $\[m\]^U$ (in any other case we will fail either in uniformity or in independence). This is what is meant by "$h$ should be anyone of these functions".

---
Tags: algorithm-analysis, data-structures, space-complexity, hash-tables, hashing
---


# Question
Title: Splitting a group of numbers into $k$ sorted groups
I have this first task:
You have a set of numbers $S =\\{ \dots \\}$ of length $n$.
And a number $k$.
Both $n$ and $k$ are powers of $2$ and: $1 \< k \< n$

Your task is to write an algorithm (pseudo-code) that splits $S$ into $k$ sets (which have the same length each): $S\_1 , S\_2 , \dots, S\_k$ such that all the numbers in $S\_i$ are smaller than all the numbers in $S\_{i+1}$ for all $1 \leq i \leq k-1$ in time complexity of $O(n \cdot k)$ (end of task 1)

**The second** (another question, but related to the first one) task is the same, but suggesting a faster algorithm - psuedo-code (time complexity -wise)

For example:

For $S = \\{11,5,2,7,1,13,15,16 \\}$ and $k = 4$ I would return (right to left):
$\\{16, 15 \\} , \\{13, 11 \\} , \\{5, 7 \\} , \\{1, 2\\}$
notice the order of the numbers inside these sets does not have to be in any particular order.

My go:
What have I not tried.. god:

1. I thought of doing a bucket sort.
2. Maybe choose a random pivot and do a select for each group.
3. Make $k$ empty sets of length $\frac{n}{k}$ each ("in advance") and then choose the $k$-th smaller elements each iteration.
4. make $k$ empty sets of length $\frac{n}{k}$ "in advance" and then putting each number in the first one, and once we come across a bigger number we move the smallest of them to the next set like this for the example above (explicit details below):

## This is the algorithm I have so far (number 4):

First we have an empty $k=4$ sets of length $\frac{n}{k} = \frac{8}{4} = 2$ and then comes $11$, then $5$ :
$\\{11 , 5 \\}, \\{ , \\}, \\{ , \\}, \\{ , \\}$ and then $2$ comes but it's smaller than $5$ or $11$ so $\\{11 , 5 \\}, \\{2 , \\}, \\{ , \\}, \\{ , \\}$ then comes $7$ and it is larger than $5$ so it replaces it and moves the $5$ to the next set:
$\\{11 , 7 \\}, \\{2 , 5\\}, \\{ , \\}, \\{ , \\}$ etc...

it should work but I am not sure what is the running complexity. For each set ($k$ times) I have to run $\frac{n}{k}$ iterations (the length of each subset)

Nothing works if I understand it correctly. Nothing here gives me time complexity of $O(n \cdot k)$ ...
I did not even start thinking about the second solution.. because I can't get pass the first one..

I would appreciate your help!

# Answer
> 1 votes
Your second idea seems to be close. Here is the actual algorithm (no random pivot is required):

1. Find the $i{n\over k}$'th order statistic for every $1\le i\le k$. This will take $O(n)$ each time for $k$ values: $O(nk)$.
2. For every such $i$, put all elements with values between the $i{n\over k}$'th and the $(i+1){n\over k}$'th order statistics in the $i$'th bucket. For each $i$ it would cost $O(n)$ and there are $k$ different values for $i$, thus total of $O(nk)$.

Both steps take $O(nk)$ and therefore the entire algorithm runs in $O(nk)$ as required

**Hint for the second question:** think how you can combine this algorithm with a coarse version of quicksort

---
Tags: algorithms, complexity-theory, time-complexity, sets
---


# Question
Title: Can a 600 MB text file with digits of the square root of 2 be compressed to 600 KB?
I have a simple script to calculate gaps in a sequence of digits of the square root of 2 (or any other multi-precision constant). As input, I generated files with the *bigfloat* module in Python:

```
from bigfloat import sqrt, precision

MAX_PRECISION_BITS: int = 1 << 30
CONSTANT = 2

precision_bits: int = 8
while precision_bits < MAX_PRECISION_BITS:
    with open(f"input/square_root_of_{CONSTANT}_with_{precision_bits}_bits.txt", 'w') as fd:
        fd.write(str(sqrt(CONSTANT, precision(precision_bits))))
        fd.flush()
    precision_bits *= 2

```

Although I can run the script any time, I decided to compress the input files, and I was surprised that a 646.5 MB got compressed to 632 KB, ie less than 1 MB! This value was obtained with the standard Zip method that is available in Mac OS X. I performed a diff command in the original and expanded file to check for possible differences and none was found.

I understand that every decimal digit takes about 3.32 bits, and the square root of 2 is conjectured to be normal, so I was expecting a compression to 40% or so.

How is this compression attained?

# Answer
> 3 votes
Clearly that's a way too good compression rate. $\sqrt{2}$ is not a rational number, so the decimal expansion will not start repeating. So there has to be something really fishy going on.

I run your script, and looked at the resulting file.

On my machine, the file `square_root_of_2_with_536870912_bits.txt` contains 161.614.250 digits, and the last 161.597.755 digits are all zeros. Only the first 16.495 digits are different from zero.

So given that pretty much almost everything in the files are zeros, it's not unexpected that the compression rate is so high.

---

I'm not experienced with the `bigfloat` package, so I can't tell if the bug is in your program or in the package itself. If you can't figure the error out yourself, open an issue on their Github page.

Btw, from those 16.495 digits, only about 5.000 of those are correct.

# Answer
> 1 votes
At the risk of stating the obvious, it depends on your compression method. 600MB of digits of the square root of 2 can be compressed to the code that you have written in this very question, which is smaller than 1KB.

# Answer
> 0 votes
Pertaining to your specific question and as stated by Jakube, √2 is an irrational number, in which case there are no specific patterns that should exist in the fractional digits to the right of the decimal point. I understand that ***bigfloat*** is an arbitrary precision arithmetic package; however, it appears to be somewhat limited if the decimal precision is approximately 16,500 digits after the decimal point (with the remaining digits being zero).

As I am sure you're aware, the whole point of lossless text compression is to reduce symbol redundancy. At present, there is no way that one could conceivably compress a 614400 KB (600 MB) text file of random ASCII symbols (i.e., √2 to 600 MB, which is 629,145,600 numbers in a random sequence) into a 600 KB compressed archive. In this context, 99.9% losslesss compression efficiency is not possible. It appears that you achieved an extremely high level of compression because of the limits of ***bigfloat***. Your script generated millions of zeroes when computing √2, which constitutes a massive amount of redundancy.

---
Tags: data-compression, python
---


# Question
Title: In a LP problem Ax = b, how to solve for A instead of x?
I have a multi-objective linear programming problem of the form **Ax** = **b**, where **A** is a matrix and **x** and **b** are vectors. **x** is known, and I'm looking to minimise each row of **b** by solving for **A**.

Constraints are:

1. Each column of **A** must add up to 1.
2. **A** will start with some values being 0, and those must remain 0. In other words, **A** is sparse.

I know of algorithms to solve MOLPs like simplex and Benson's, but I'm seeing differences between how the inputs to those algorithms are expressed and how my problem is framed. What I'm looking for is how to *transform or reframe my problem* so that it can be solved by these algorithms, or alternatively, how an algorithm can be changed to accommodate the extra constraints.

The main differences I see are:

1. In most MOLPs of the form Ax = b, A is known and x is the thing to be solved for. In my problem, it's the opposite. x is fixed, and A is what needs to be solved for.
2. In my problem, x can contain both positive and negative values, and the objective is to get each row of b as close to zero as possible. I feel like this can be dealt with with slack variables, though, so that's not as much of an issue.
3. How to incorporate my constraints of **A**'s columns adding up to 1, and **A**'s sparcity.

# Answer
Let $a\_{ij}$ represent member of matrix $A$. This can either be the constant $0$ if you want $a\_{ij}$ to be $0$ in the solution matrix, or a variable for a linear programming problem. Then you want to add linear constraints:

\begin{alignat}{2} &\\!\min\_{a} &\qquad& \sum\_{i} s\_i\\ &\text{subject to} & & \forall j \left(\sum\_{i}a\_{ij} \leq 1 + \epsilon \right),\\ & & & \forall j \left(\sum\_{i}a\_{ij} \geq 1 - \epsilon \right),\\ & & & \forall\_i \left(\sum\_{j}a\_{ij}x\_j \leq s\_i\right),\\ & & & \forall\_i \left(\sum\_{j}a\_{ij}x\_j \geq -s\_i\right). \end{alignat}

This finds the optimal matrix $A$, with the desired elements set to $0$, that has columns adding up to $1$ (within a certain precision) and minimizes $\left\lVert Ax\right\rVert\_1$.
> 0 votes

---
Tags: optimization, linear-programming, matrix, matrix-multiplication, simplex
---


# Question
Title: Instantiating a class with a sig'd type in Coq
I can easily define a class that corresponds to the notion of a "monoidal structure" on a type `M` via

```
Definition associative {X:Type} (f : X -> X -> X) : Prop := forall x y z:X, f (f x y) z = f x (f y z).

Definition opId {X:Type} (f : X -> X -> X) (e : X) : Prop := forall x:X, f e x = x /\ f x e = x.

Class Monoid (M:Type) :=
  { binM : M -> M -> M ; idM : M ; assocMProof : associative binM ; idMProof : opId binM idM }.

```

and then instantiate it, for instance, with the type of endomorphisms over a given type with operation being composition:

```
#[refine] Instance compMon {X:Type} : Monoid (X -> X) :=
{
binM f g := fun x => f (g x) ; idM := fun x => x
}.
Proof.
  - unfold associative. reflexivity.
  - unfold opId. intro. split. reflexivity. reflexivity.
Defined.

```

but how would I, for example, go about defining the monoidal structure on the set of *injective* endomorphisms over a type? (Or even better, formalizing the notion that `binM` in `compMon` restricts to such a monoidal structure?) I presume I would want to define `injective` and then instantiate `Monoid {f : X -> X | injective f}` but not only would that seem to entail defining a new binary operation (which takes functions `f, g` and proofs of injectivity `i, j` and produces a new function with a new proof of injectivity) and a new identity, it seems that said binary operation wouldn't even be associative (of course $f \circ (g \circ h) = (f \circ g) \circ h$ as functions, but the proofs of injectivity aren't the same?). What am I missing?

# Answer
> 2 votes
You are missing propositional extensionality. It is not provable in straight Coq but you can assume it. And while you are at it, if your going to do math, you will also want function extensionality. Both forms of extensionality follow from univalence, which is also an extensionality principle, except that this one is for the universe of types.

If you prefer to avoid all this you can go down the road of setoids: you equip every types with an equivalence relation that serves as the equality relation. You then have to keep proving that your functions preserve these relations. It's a lot of "fun".

---
Tags: coq
---


# Question
Title: complexity of dividing set of number with constraints
I've been thinking about a division problem for groups that I haven't found a dynamic programming solution and I'm trying to analyze the complexity of the problem.

There is a set of $n$ positive numbers ($S$), a vector of group sizes (let's call it $Sizes$), and a parameter $Y$. Find a way for divide the $n$ numbers into groups that their size describes in $Sizes$ s.t. the $constraint$ in close as possible to $Y$.

For example, $ S = \\{1,1,2,2,3,4,4,7,9,11\\}$, $Sizes = \[2,2,3,3\]$, $Y=2$ and $constraint =$ the variance of the group. Of course that the $constraint$ could be changed in other cases. But this is representative example.

Has this problem any dynamic programming solution? or that the complexity is exponential (which means $NP$ problem)?

Which approximation approaches can help me in this case?

Thanks in advance!

# Answer
The difficulty of your problem heavily depends on "constraint".

For example if $n=3k$, $\text{size}=\[\underbrace{3,3,3,...}\_{k\text{ times}}\]$, and the constraint is that the sum of the numbers each group must be equal, then your problem is strongly NP-hard since it is exactly $3$-partition.

The same problem with groups of size $2$ is polynomial.

Notice that both problems are in $\mathsf{NP}$ and that being in $\mathsf{NP}$ does **not** mean that the complexity to solve it is exponential.
> 0 votes

---
Tags: complexity-theory, dynamic-programming, np
---


# Question
Title: A pretrained model for mathematical equations characters detection
I am working on a project to convert equations to LaTeX code. After segmenting out the characters, I got stuck on the detection part and was looking for some pre-trained model that could detect characters of the equation for later conversion to LaTeX. Is there any such pre-trained model available on the internet that could be used in Python to identify characters. If not then can somebody share some source to find a dataset to train such kind of model in Keras? I was able to find one on GitHub but It doesn't detect symbols accurately.

# Answer
Detexify is a service that recognizes LaTeX symbols from handwritten figures. Their training dataset is freely available on Github.
> 2 votes

---
Tags: machine-learning, image-processing, pattern-recognition, python, digital-image-processing
---


title: A variation of the halting problem

text:
# Question
Title: A variation of the halting problem
Given an infinite set $S \subseteq \mathbb{N}$, define the language:

$L\_S = \\{ \langle M \rangle : M $ is a deterministic TM that *does not* halt on $\epsilon$, or, $T\_M \in S\\}$

where $T\_M$ is the number of steps that $M$ takes until it halts with the empty word $\epsilon$ as input (or $\infty$ if it doesn't halt).

> What are the sets $S$ such that $L\_S$ is decidable?

There are some more trivial cases, if $S = \\{k,k+1,k+2, \dots \\}$ for some $k \in \mathbb{N}$ then $L\_S$ is clearly decidable, as we can simulate $M$ on $\epsilon$ for $k-1$ steps and accept if and only if $M$ didn't halt. though, if we take $S= \\{k,k+2,k+4,\dots \\}$ for some $k \in \mathbb{N}$, or even simply taking $S=\mathbb{N}\_{even}$ or $S=\mathbb{N}\_{odd}$ this becomes more of a problem, because there is no prevention from it being impossible to have a finite calculation for whether the number of steps until halting will be even in the cases where it halts. Although this seems undecidable I'm not sure how to prove this.

I generally suspect that $L\_S$ is decidable if and only if $\mathbb{N} \setminus S$ is finite and $S$ is decidable

# Answer
> 1 votes
## $L\_S$ is undecidable if $S = \mathbb{N}\_{odd}$:

The problem of whether a given TM accepts $\epsilon$ is undecidable. There is a simple reduction from this problem to the problem of membership in $L\_S$ when $S = \mathbb{N}\_{odd}$. Given a TM $M$, we create a new TM $M'$ which on any input simulates $M$ on the same input, but for each step of $M$, it takes one (or any finite odd number of) extra redundant step(s). This basically makes sure that the number of steps taken by $M'$ on any input is always **even**.
Now, since $T\_{M'} \notin S$, hence, $M'$ is in $L\_S$ if and only if $M'$ doesn't halts on $\epsilon$, which in turn implies that $M$ doesn't halt on $\epsilon$. Hence, this language is undecidable.

A similar proof can be also given for $\mathbb{N}\_{even}$.

## \[Undecidable $S$ with Oracle Machines\] $L\_S$ is decidable for a set $S$ for which $\mathbb{N} \setminus S$ is not finite.

Assuming that the set $S$ need not be decidable itself, and we are going to use it as an oracle and check for decidability using oracle machines.

We construct the set $S$ as follows: for each Turing Machine $M$, let it's binary encoding be $\langle M \rangle$, and let the length of the string $\langle M \rangle$ be $n$. If $M$ doesn't halt on $\epsilon$, then we add the number $10^{n}\langle M \rangle$ to our set $S$. By construction, this set doesn't contain infinite numbers.

Now, the decider will work as follows: On an input $M$, it will check whether the number $10^{n}\langle M \rangle$ is in $S$. It will accept $M$ if the number if found, else we can be sure that the machine $M$ will halt, and hence we simulate $M$ on $\epsilon$ until it halts while keeping the count of the number of steps taken by $M$. We finally accept or reject $M$ on the basis of whether this count is in $S$ or not.

Hence, this language is decidable for a set $S$ for which $\mathbb{N} \setminus S$ is not finite.

## \[Decidable S\]

When the set $S$ is decidable, it will be interesting to know whether the hypothesis that "$\mathbb{N} \setminus S$ is finite" holds. I suspect that the answer would be affirmative.

Let $S' = \mathbb{N} \setminus S$ be infinite set. If $S'$ has "simple" subsequence in it (say, an Arithmetic Progression), then we can prove that $L\_S$ would be undecidable by a proof similar to the one in the case of $S = \mathbb{N}\_{odd}$. The idea is simply to run a construct a TM $M'$ which simulates $M$, and if $M$ halts, then jump to the next hole in $S$. $M'$ will be in $L\_S$ iff $M$ halts.

This idea doesn't seem to work when $S'$ is a *difficult* set; by which I mean that checking the membership is hard in terms of time complexity.

---
Tags: turing-machines, undecidability, decision-problem
---


# Question
Title: why is $\Pi_2$ smaller than $NP\cap coNP$
Consider the language $A=\\{(\phi\_1, \phi\_2) | \phi\_1 \in SAT, \phi\_2\in \overline{SAT} \\}$. What is the smallest class that $A$ is known to belong to?

Apparently, the answer is $\Pi\_2$, although I thought it was $NP \cap coNP$, since if we have a non-deterministic machine $M\_1$ that decides $SAT$ and another non-deterministic machine $M\_2$ that decides $\overline {SAT}$, then we can define a machine $M\_3$ that on input $(\phi\_1, \phi\_2)$, runs $M\_1$ on $\phi\_1$ and $M\_2$ on $\phi\_2$, and only accepts if both machines return *True*. If the input does belong to $A$, then for some set of nondeterministic choices, we know $M\_3$ will accept. If the input doesn't belong to $A$, then either $M\_1$ or $M\_2$ always return *False*, and so $M\_3$ always rejects.

My first question is whether my explanation correctly shows $A \in NP \cap coNP$. More importantly though, why is $\Pi\_2$ smaller than $NP\cap coNP$!?

# Answer
You seem to be using the following definition of $\mathsf{NP} \cap \mathsf{coNP}$: it consists of all languages of the form $L\_1 \cap L\_2$, where $L\_1 \in \mathsf{NP}$ and $L\_2 \in \mathsf{coNP}$. However, in reality $\mathsf{NP} \cap \mathsf{coNP}$ consists of all languages $L$ such that $L \in \mathsf{NP}$ and $L \in \mathsf{coNP}$.
> 1 votes

---
Tags: complexity-theory, decision-problem, complexity-classes
---


# Question
Title: Why do AI researchers seem to think that consciousness is a computation?
Disclaimer: I am just an undergraduate student so my exposure to a lot of things is certainly limited.

I am not sure about the actual popularity of the idea that consciousness is a computation but my impression is that it is very widespread. I lost count to how many times I saw, sometimes very serious scientists, claim that we are just decades away from an actually intelligent AI (or AGI).

I also noticed a similar underlying premise with Machine Learning's "Neural Network" which is more or less exactly an implementation of the computational model of consciousness (which as far as I understand it \[the model in the next sentence\], assumes the Hodgkin-Huxley model to be true even though we don't actually really know that).

Am I wrong? Is it actually not as widely accepted and popular as I think it is? If not, then why is it this widely accepted as fact?

# Answer
Consciousness as a computation is not by any means a scientific fact. Firstly because there's no universally accepted definition of consciousness.

General AI does not have either a widely accepted definition. There are two hypothesis in relation to consciousness: Weak AI states that you can achieve AGI with the computational models that we know e.g. without "consciousness." Strong AI, on the other hand states that there's something beyond our known computational models that is needed to achieve AGI.

Neural networks as used in machine learning are modeled in biological nervous systems but I don't think anyone has claimed that consciousness or even AGI can be expected from their implementation.

Some proposed consciousness theories worth mentioning are:

Daniel Benett's: Consciousness is nothing special. It's an illusion that you have control of your own decisions. He backs it up with some experiments that have been done where subjects think they have reached a given decision. In the experimental setup, however, it's demonstrated that before the subjects confirm that they've taken their decision an external observer can already determine the decision that the subject will take.

Douglas Hofstadter's theory of consciousness is based on the idea that consciousness is an effect achieved through computational deep recursion.

However, as I mentioned in my first point, consciousness is not scientifically defined to be even possible to set up a proper experiment that could determine wether consciousness can be achieved through computation or not.
> 2 votes

---
Tags: artificial-intelligence
---


# Question
Title: Correctness of Strongly Connected Components algorithm for a directed graph
I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$.

The algorithm is the following :

1. Execute DFS on $G$ (starting at an arbitrary starting vertex), keeping track of the ﬁnishing times of all vertices.
2. Compute the transpose,
3. Execute DFS on $G^T$, starting at the vertex with the latest ﬁnishing time, forming a tree rooted at that vertex. Once a tree is completed, move on to the unvisited vertex with the next latest ﬁnishing time and form another tree using DFS and repeat until all the vertices in $G^T$ are visited.
4. Output the vertices in each tree formed by the second DFS as a separate strongly connected component.

My question is :

1. What is the intuition behind this middle step of computing a transpose?

# Answer
Transposing the adjecency matrix $A$ does

$\qquad A\[i,j\] = 1 \iff A^T\[j,i\] = 1$.

In terms of graphs, that means

$\qquad u \to\_G v \iff v \to\_{G^T} u$.

In other words, transposing reverses the direction of all edges. Note that $G^T$ has the same strong components as $G$.

The algorithm you are looking at is Kosaraju's algorithm. Be carful with your notion of "finishing time": it's not the time the node is visited, but when the search has traversed the subgraph reachable from it. Wikipedia proposes to use a stack to manage this, which I think is a good idea.

Why is it correct to use $G^T$, intuitively? Assume $x$ is the first node of its strong component visited by the DFS.

* The DFS on $G$ traverses the whole strong component of $x$ after reaching $x$, plus some others via edges that leave the component.
* Since we use a stack order for remembering the order of nodes, $x$ is also the first node of its strong component visited (as starting node, even) in the second phase.
* Since $G$ and $G^T$ have the same strong components, all nodes in the strong component of $x$ are visited when searching $G^T$ from $x$. Those edges leaving the component in the first phase point in the wrong direction in $G^T$ and are thus not followed. All edges leaving the component of $x$ in $G^T$ have already been removed because of the stack order.
> 15 votes

# Answer
My understanding:

When you execute DFS on any DAG graph keeping track of the finishing times, the **only** thing you can guarantee is that **sink node will never get the highest finishing time \[1\]**. But at the same time, **the lowest finishing time may appear in any component of the graph**. Hence, it makes the lowest finishing time kind of useless.

Basically, the fact **\[1\]** is useless **in the original graph** as well, but it is very useful **in the transposed graph**. When you transpose, this statement leads to the following:

In the transposed graph, the node that was a sink in the non-transposed graph **will always get the highest finishing time**.
> 3 votes

# Answer
1. strongly connected components in $G$ and $G\_{transpose}$ will remain the same (implied by definition of strongly connected components)
2. any graph can be divided into strongly connected components - let's call these components $C\_1, C\_2, C\_3 \dots C\_N$

After first round of DFS and sorting in descending order of finish time

Let's say the component $C\_i$ has the node with highest finish time. One tricky thing to observe that this component $C\_i$ which has highest finish time cannot have any outside edge coming into the component $C\_i$.

To prove the above fact (by contradiction):-
let's consider that there exists a component $C\_j$ from which there is an edge into component $C\_i$.
And $C\_j$ has no node which has larger finish time than $C\_i$'s node -

but this is not possible because during DFS $C\_j$ will have then larger finish time. (Even if you start DFS from any node - you can check by yourself.)

Now you have component $C\_i$ and no outside edge is coming inside $C\_i$ so if you transpose the graph the components will not change (because strongly connected) but the edges connecting them will be reversed.

Therefore $C\_i$ have no edge going out to other components. That's all we wanted;
if you apply DFS on this graph starting from any node of $C\_i$ you will traverse only through this $C\_i$ component and will not enter into others.

This way you have separated $C\_i$ from graph.

Hope that helped,
comment if you have any doubt, I'll try to reply asap
> 2 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Hash function, $h(k) = \lfloor km \rfloor$ is simple uniform for real $k$ independently, uniformly distributed in the range $0 \leq k < 1$
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following statement:

> If the keys are known to be random real numbers $k$ independently and uniformly distributed in the range $0 \leq k \< 1$ , the hash function
>
> $$h(k) = \lfloor km \rfloor$$ satisfies the condition of simple uniform hashing.

Now what I can understand that they are probably considering uniform disturbution in the "continuous" sense and not in the discrete sense. Had it been in the discrete sense then suppose for $n$ keys the probabity mass function (p.m.f) shall be constant and equal to $1/n$ and so it shall be equally likely for each key to be used in the hashing there-by yeilding the desired result.

But we seem sort of in trouble if the distribution being referred to is continuous (I feel so because of the line: "uniformly distributed in **the range $0 \leq k \< 1$**")

Let $f(x)$ be the associated probability density function (p.d.f) and from the given information we have $f(x)=1$,(which is quite easily found, integrating $f(x)$ in the range $0$ to $1$ and equating it with $1$ and noting that in uniform distribution the p.d.f is a constant).

Now though the p.d.f is a constant but p.d.f is not the probability. Rather probability at a spectrum point is $0$. Now how to use this result to get to the claim of the authors.

Or am I entirely at fault considering the distribution to be continuous?

(There is an answer here, but it does not go into this detail as the question there is different after all).

# Answer
$h\in \[m\]^U$ satisfies the simple uniform hashing assumption if when $x\in U$ is chosen uniformly at random, then $h(x)$ is uniformly distributed over $\[m\]$, or equivalently $\forall i\in\[m\]: \Pr\limits\_{x\in U}\[h(x)=i\]=\frac{1}{m}$. In our case we have:

$\Pr\[h(x)=i\]=\Pr\big\[\lfloor mx \rfloor=i\big\]=\Pr\[i\le mx \< i+1\]=\frac{i+1}{m}-\frac{i}{m}=\frac{1}{m}$.

We used the fact that if $x$ is uniformly distributed over $\[0,1\]$ then $\Pr\[a\le x\le b\]=b-a$ (the equality holds with all four combinations of $\le$ and $\<$).
> 2 votes

---
Tags: probability-theory, probabilistic-algorithms, hashing
---