# Question
Title: What is the language generated by a given grammar
> Given the grammar
> $s \to aSb \mid bSb \mid a \mid b$;
> what is the language generated by the grammar over the alphabet $\\{a,b\\}$?

When I was solving this question I was a bit confused about the language generated by this grammar. Would be set of all palindromes? Or would the language generated by the above grammar be that of all odd length palindromes?

Is it possible that a palindrome generated by above grammar be of odd length only as there is no rule for $S \to \varepsilon$?

# Answer
> 5 votes
The language of this grammar is all strings of the form $wb^n$ where $w\in \\{a,b\\}^\*$, and $|w| = n+1$. If I abuse the notation a bit, it is $\Sigma^{n+1}b^n$.

If perchance you mean $S \rightarrow aSa \ | \ bSb \ | \ a\ | \ b$, then the language contains all palindromic strings of odd length.

# Answer
> 1 votes
S→aSa | bSb | a | b

This grammar accepts all palindromic strings of odd length For Ex: aaa is generated by S-\>aSa and S-\>a and for string abbba : S-\>aSa , S-\>bSb and S-\>b aSa abSba abbba and hence we get abbba whose palindrome would be abbba itself.

# Answer
> -1 votes
S-\>aSa S-\>bSb S-\>a S-\>b solution now put any value in "S" in the L,H,S it will give a string of odd palindrome e.g aaa,aba,bbb,bab, abSba=ababa or abbba etc

# Answer
> -2 votes
The strings accepted by language are {a, b, aaa, bbb, aba, bab, ..}.Therefore more specific answer is " All of these strings are odd length palindromes." Yes it is odd length because S doesn't go to epsilon.

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


# Question
Title: Difference between selecting a large pool of individuals for reproduction, and selecting two parents specifically
I have implemented a genetic algorithm for an optimization problem and I'm now trying to improve it to see if I can find better solutions or faster convergence.

I am confused about the *selection* part of the algorithm and how it relates to *selecting parents for cross-over*. In my mind these things are **not** the same yet many resources seem to treat them the same, and I can't figure out how or why.

As far as I understand the terms:

1. **Selection** means: selecting a subset of the current population (e.g. half) which will reproduce to form the new generation. Non-selected individuals are discarded. Selection should be based on fitness in some way such that more fit individuals are selected with higher probability (but bad individuals can still be selected for sufficient genetic diversity).
2. **Selecting parents for cross-over** means: from the group of selected individuals, take *two* parents to cross-over and form *one* child. (I know schemes are possible with more than two parents and/or more than one children but let's keep it simple). This step should be repeated until I filled the new population.

Let's say I have a population of 50 and **select** half of them, leaving me with 25 parents which will now reproduce to form 50 new individuals. Since there are only 25 parents and I need 50 children, probability is high that one parent can have multiple children. There is of course a chance that the same parent reproduces with itself giving an identical copy (ignoring mutation for now).

My point here is that the two concepts are not the same. In **1** I select many individuals that will *later* reproduce, but for now I am merely letting the non-selected individuals die. In **2** I then select *two* parents specifically to cross-over and form one new individual. It is entirely possible (though obviously very unlikely) that I keep selecting the same 2 parents from my pool 25 and ignore the others.

I know of various selection operators but I am confused about which is applied to which scenario. For example:

* Tournament selection: grab a few (e.g. 2 or 4) individuals at random, and then take the best. This gives me just *one* individual. I can use this 25 times to select the 25 individuals (**1**), or I can use this twice on the group of selected individuals to select two parents for reproduction (**2**). Which one is it?
* Roulette wheel or fitness proportionate selection: grab an individual at random but with probability based on their fitness. Again: I can use this 25 times to form my pool of selected individuals, or I can use it just twice on that subset of individuals to select the two parents. Which one?
* Stochastic universal sampling (SUS): sample several individuals at equally spaced intervals based on fitness. Here it seems clear I am selecting *multiple* individuals at once (though I suppose it could be "2"), so it seems likely this can be used to form my pool of 25 individuals.
* Truncation: simply take the best x% and discard the rest (I know this isn't good for genetic diversity). Clearly this can be used to select the pool of 25 individuals (e.g. discard the worst 25) but how do I now proceed to select two parents?

In general I can apply all of these selection operators to select a large group of individuals, but then I still don't know how to select (from that subset) two parents to reproduce. Is this secondary selection just random? Or should I take fitness into account again here (seems counterproductive, I already selected on fitness previously)? Or should I make sure every parent is equally selected?

# Answer
The approach defined in **1** is known as `Elitism approach` or `Elitism based selection`, which is usually done by selecting the fittest individuals. link1 and link2.

The approach defined in **2** is commonly known as crossover where 2 individuals are repeatedly selected via different algorithms like *Tournament selection, Roulette wheel, etc.* until the max population is reached.
> 0 votes

---
Tags: genetic-algorithms
---


# Question
Title: Analyzing asymptotic notation $\sqrt n = O(\log^2 n)$
I am trying to determine whether $f(n) = \sqrt n$ is in $O(g(n))$, $\Omega(g(n))$, or $\Theta(g(n))$ where $g(n) = \log^2 n$.

The answer says that only $f(n) = \Omega(g(n))$ is correct, but why isn't $f(n) = O(g(n))$ correct as well?

The formal definition is $f(n) = O(g(n))$ means $c\*g(n)$ is an upper bound on $f(n)$. Thus there exists some constant $c$ such that $f(n)$ is always $\log c\*g(n)$ for large enough $n$.

If we take $n = 100 \\; 000$ (I think that is large enough), then

$$\begin{align\*} \sqrt{100 \\; 000} &\leq c\*\log^2 100 \\; 000 \\ \sim 316 &\leq c\*25 \end{align\*}$$

Here we see there is indeed a $c$ such as $c=15$ that will satisfy the inequality. This doesn't make sense though because then by this logic there should be a $c$ that will satisfy *every* inequality. Am I interpreting the definitions wrong?

# Answer
I'll assume you're using base 10 logs and the convention $\log^2(x) := \log(x)^2$ since this accords with the numbers you're giving.

It's not true that $\sqrt{n} \< 15 \log\_{10}(x)^2$ for arbitrarily large $n$. For instance let $n$ be a million. Then the LHS is 1,000 and the RHS is $15(6)^2 = 540$.

More generally, there's no value of c that will work for all sufficiently large n, as you can see by working out the limit of $\sqrt{x}/log(x)^2$ using techniques from your calculus class.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Proving the singleton language {x} is regular for all x ∈ Σ*
So I'm aware that the singleton language is in fact regular for all x ∈ Σ\*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would also be appreciated! As of now I'm just aware of it as a property, but I don't have a good grasp on why it is regular.

# Answer
$\Sigma^\*$ is a set of finite strings. There are infinitely many of them, but each one is finite – just like there are infinitely many natural numbers but each one of them is finite.

So, for any $x\in\Sigma^\*$, $\\{x\\}$ is a finite language (it contains one string) of finite strings (because everything in $\Sigma^\*$ is finite), so it's regular.
> 1 votes

---
Tags: regular-languages, proof-techniques, sets
---


# Question
Title: Must the champion of an entire tournament beat the champion of a possible tournament among other players?
I have a list of "players" of a "tournament". Any two *adjacent* players may "compete", which results in the loser being thrown out of the tournament. Winning is not transitive. The winner of a given competition between two players is known, but the order of competitions is not. Suppose that I have some tournament of the form $p\_1, p\_2, p\_3, ..., p\_n$ and I know that $p\_1$ may win the entire tournament (depending on the order of competitions). Can I show that $p\_1$ must beat some possible winner of a tournament on just $p\_2, p\_3, ..., p\_n$?

I originally came to this while proving the correctness of an algorithm to determine the list of possible winners of a general tournament, but this specific subproblem is giving me trouble.

To begin an attempt at a solution, I offer that in the contrary case, $p\_1$ must *only* compete against and beat some sequence of "losers" (players who cannot win the tournament on just $p\_2, ..., p\_n$ no matter the order played), with no winners losing to $p\_1$. This implies that at some point, a loser must defeat a winner. This may be impossible? I can't prove that, and I don't know whether that's even true.

# Answer
Here is a proof by induction. The base case, $n = 2$, is clear.

Now consider a tournament in which $p\_1$ wins. Suppose first that the first competition doesn't involve $p\_1$. Let the new set of players be $p\_1,P$. By induction, we know that $p\_1$ must beat one of the possible winners of the tournament in $P$, say $p\_i$. Since the first competition didn't involve $p\_1$, $p\_i$ can also win the tournament on $p\_2,\ldots,p\_n$, completing the proof in this case.

Suppose next that the first competition has $p\_1$ beating $p\_2$. Applying the induction hypothesis, we know that $p\_1$ must beat one of the possible winners of the tournament in $p\_3,\ldots,p\_n$, say $p\_i$. If $p\_i$ beats $p\_2$, then $p\_i$ can also win the tournament on $p\_2,\ldots,p\_n$, and we're done. If $p\_2$ beat $p\_i$, then $p\_2$ can win the tournament on $p\_2,\ldots,p\_n$, and so we're again done (since in the first competition, $p\_1$ beat $p\_2$).
> 4 votes

# Answer
We are talking about **single-elimination tournament** throughout.

Here is a proof to confirm a positive answer to the question.

Let $p\_1$ win an entire tournament $T$. For every other player $q$, consider its losing chain $q=l(0), l(1),l(2),\cdots, l(d\_T(q))=p\_1$, where player $l(i)$ loses to player $l(i+1)$ in $T$ for all $i$, $0\le i\lt d\_T(q)$. We call $d\_T(q)$ **the losing degree of player $q$ in $T$**.

Let $w$ be the player among champions of all possible tournaments among players other than $p\_1$ such that its losing degree $d\_T(w)$ is the smallest, i.e., $w$ is "the closest to win" in $T$. Suppose $w$ loses to $s$ in $T$, i.e., $d\_T(s)=d\_T(w)-1\<d\_T(w)$. If $s$ is not $p\_1$, then $s$ can be the champion of a possible tournament among players other than $p\_1$ as well, which contradicts the minimality of $d\_T(w)$. So $s$ must be $p\_1$. The proof is done.

---

> To begin an attempt at a solution, I offer that in the contrary case, $p\_1$ must only compete against and beat some sequence of "losers" (players who cannot win the tournament on just $p\_2,\cdots,p\_n$ no matter the order played), with no winners losing to $p\_1$. This implies that at some point, a loser must defeat a winner. This may be impossible? I can't prove that, and I don't know whether that's even true.

"A loser must defeat a winner" is indeed impossible. To continue your approach, you need to find and take advantage of **the extreme case** as shown in the above proof. That is, among all cases of "a loser defeat a winner", select the winner that is closest to win the entire tournament.

---

Here are several related easy exercises.

**Exercise 1.** (One minute or less) Show that $s$ can be a possible winner of a tournament among $p\_2, p\_3,\cdots, p\_n$ indeed in the above proof.

**Exercise 2.** For each player $p$, let $d(p)$ be the smallest $d\_T(p)$ among all possible tournament $T$ on all players. Call $d(p)$ the losing degree of $p$. Show that $d(p)\ge d(q)$ if $p$ plays worse than $q$. Give an example when the equality does hold.

**Exercise 3.** Generalize the above to tournaments among the vertices of a general directed graph $G$ that has no parallel edges, whose edge $(v\_i,v\_j)$ means vertex $v\_i$ plays worse than vertex $v\_j$.
> 2 votes

---
Tags: correctness-proof, game-theory
---


# Question
Title: Return copy of array, each element product of all others, constant additional space, no division
**Question**: I am trying to solve question `6.10.1` from Elements of Programming Interviews. The task is as follows:

Given an array $\<a\_1, \ldots, a\_n\>$ of fixed-length `int`s, devise an algorithm which returns a new array $\<b\_1, \ldots, b\_n\>$ where each $b\_i$ is the product of all $a\_j$ with $j \neq i$. That is, each element of the result is the product of all other elements in the original array. Division is *not* allowed, and the algorithm must run in $O(n)$ time and $O(1)$ additional space.

**Example**: $\<1, 2, 3\>$ should be updated to $\<2\*3, 1\*3, 1\*2\>$.

# Answer
> 5 votes
# A variation of a solution left by a commenter called Vince

Given input $a = \<a\_1, ..., a\_n\>$.

1. Allocate result array $b = \<b\_1, \ldots, b\_n\>$. Set $product = 1$.
2. For $i \in \[1, n\]$, set $b\_i = product$ and set $product = product * a\_i$.
3. Set $product = a\_n$. For $i \in \[n - 1, 1\]$, set $b\_i = b\_i * product$, and set $product = product * a\_i$.
4. Return the array $\<b\_1, \ldots, b\_n\>$.

This solution runs in $O(n)$ time and $O(1)$ space additional to that allocated for the result.

# Answer
> 4 votes
# My in-place $O(nlogn)$ time, $O(logn)$ additional space solution

Let $a = \<a\_1, ..., a\_n\>$.

Define the function $\operatorname{f}(\texttt{start}, \texttt{end}) : \texttt{int}$. $\texttt{start}$ and $\texttt{end}$ define the inclusive start and end indices in $a$. The function returns the product of *all* elements in the range. $\operatorname{f}(1, n)$ updates $a$ in-place to the desired result.

Define $\texttt{length} = (\texttt{end} - \texttt{start}) + 1$. Run the appropriate of the following alternatives:

1. If $\texttt{length} = 1$, set $a\_{start} = 1$ and return the original $a\_{start}$.
2. If $\texttt{length} = 2$, swap $a\_{start}$ and $a\_{end}$ and return their product.
3. If $\texttt{length} \> 2$:
    * Set $\texttt{leftEnd} = \operatorname{floor}(\texttt{length} /2)$.
    * Set $\texttt{productLeft} = \operatorname{f}(\texttt{start}, \texttt{leftEnd})$.
    * Set $\texttt{productRight} = \operatorname{f}(\texttt{leftEnd} + 1, \texttt{end})$.
    * For $i \in \[\texttt{start}, \texttt{leftEnd}\]$, replace $a\_i$ with $a\_i * \texttt{productRight}$,
    * For $i \in \[\texttt{leftEnd} + 1, \texttt{end}\]$, replace $a\_i$ with $a\_i * productLeft$. Return $\texttt{productLeft} * \texttt{productRight}$.

**Complexity**: At each level of recursion, we call $\operatorname{f}$ once on each half of the input, and then we multiply each half with the product from the other half. This gives $O(nlog(n))$ time. The maximum allocation size at each call level is $O(1)$, and there are $log(n/2)$ levels of recursion, so this means $O(log(n))$ additional space allocation.

---
Tags: algorithms, algorithm-analysis, time-complexity, space-complexity
---


title: heap pop creates unbalanced tree?

text:
# Question
Title: heap pop creates unbalanced tree?
say you have a min-heap. Popping removes the root and replaces it with the value of one of the leaves and then heapifies. couldnt this last heapify result in an unbalanced tree? is there something you have to do to maintain the balance of the tree?

# Answer
When popping the root, it is first replaced by the very last element, and then a *heapify* operation is performed to maintain the heap invariant, namely, that every node is smaller than its children.

Since we are removing the very last leaf, the heap always remains balanced, in the sense that all levels but the last will be full, and the last level will consist of a prefix of the set of potential vertices.

The three steps are illustrated in the Wikipedia article. We start with a max-heap:

We remove the root, and replace it with the very last element:

Finally, we perform a *heapify* operation on the root:
> 4 votes

---
Tags: data-structures, heaps
---


# Question
Title: Logic behind O(n) solution for 'Maximum length sub-array having given sum'
I am unable to understand the logic behind `O(n)` solution of this classical problem- `Maximum length sub-array having given sum` (negative numbers included),

I read that it can be solved in `O(n) time complexity and O(n) space complexity`, but the logic behind it is still unclear to me. I have read this solution:

1. Initialize **sum = 0** and **maxLen = 0**.
2. Create a hash table having (**sum, index**) tuples.
3. For i = 0 to n - 1, perform the following steps:
    1. Accumulate arr\[i\] to **sum**.
    2. If sum == k, update **maxLen** = i + 1.
    3. Check whether **sum** is present in the hash table or not. If not present, then add it to the hash table as (**sum, i**) pair.
    4. Check if (**sum - k**) is present in the hash table or not. If present, then obtain index of (**sum - k**) from the hash table as **index**. Now check if maxLen \< (i - index), then update **maxLen** = (i - index).
    5. Return **maxLen**.

Examples:

```
Input : arr[] = { 10, 5, 2, 7, 1, 9 }, k = 15
Output : 4
 The sub-array is {5, 2, 7, 1}.

Input : arr[] = {-5, 8, -14, 2, 4, 12}, k = -5
Output : 5

```

Taken from this link: https://www.geeksforgeeks.org/longest-sub-array-sum-k/

Could someone please elaborate on the solution provided for this problem?

# Answer
This is an example of a dynamic algorithm. I will adapt the algorithm in the link, as I don't think that it is written in the most helpful way.

1. Initialise `sum = 0` and `maxLen = 0`.
2. Create a hash table having `(sum, index)` tuples.
3. For `i = 0 to n-1`, perform the following steps:
    1. Set `sum = sum + arr[i]`.
    2. If `sum == k`, update `maxLen = i+1`, continue from here to next iteration.
    3. Check whether `sum` is present in the hash table or not. If not present, then add it to the hash table as `(sum, i)` pair.
    4. Check if `(sum-k)` is present in the hash table or not. If present, then obtain `(sum-k, index)` from the hash table. If `maxLen < (i-index)`, then update `maxLen = (i-index)`. Return `maxLen`.

If `sum == k` at case 3.3, then we know that the sub-array `[a[0],...,a[i]]` is the maximum-length sub-array whose sum is `k`. Otherwise, we continue to 3.3. If there was no sub-array until now whose sum we equal to the current `sum`, then we add `(sum, i)` to the hash table. The reason we don't overwrite existing entries will become apparent at the end.

We now continue to 3.4. If we came across a sub-array `S` whose sum was `sum - k`, then there must be pair of the form `(sum - k, index)` in the hash table. `S` is therefore the sub-array of the form `[a[0], ..., a[index]]`.

We obtain a new sub-array `[a[index + 1], ..., a[i]]` whose sum is `k` and whose length is `i - index` as follows: Remove all elements in `S` from the sub-array `[a[0], ..., a[i]]`. Its sum must be `sum - (sum - k) = k`. Now the question is whether the length of the new sub-array `i - index > maxLen`. If it is, set `maxLen = i - index`.

Now we can see why we didn't update existing entries in 3.3. We do not want to add larger arrays (greater `index`) for a given sum. This would have made `i - index` smaller.

This is a polynomial-time algorithm, as we look at each element exactly once, and the hash table accesses are also constant time.
> 7 votes

# Answer
A sum of consecutive elements in a list can be expressed as:

$a\_j + a\_{j+1} + \ldots +a\_k = (a\_1 + \ldots + a\_k) - (a\_1 + \ldots + a\_{j-1})$

Let's write

$S\_n := a\_1 + \ldots + a\_n$

Then if we just go through the list calculating $S\_i$ and remembering which numbers we got, we can check at each step whether there's a front part we can subtract off to get a given sum of consecutive elements.
> 4 votes

---
Tags: algorithms, time-complexity, space-complexity
---


# Question
Title: Which AC-3 algorithm is being used here?
This is the illustration of the AC-3 algorithm for four queens from *exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem* by Md. Ahsan Ayub, Kazi A Kalpoma, Humaira Tasnim Proma, Syed Mehrab Kabir and Rakib Ibna Hamid.

I am confused whether this is pure AC-3 or AC-3 with backtracking. Which one is it?

# Answer
The Fig. 5 in the question depicts AC-algorithm with backtracking.

In fact, without backtracking, checking arc-consistency alone can hardly solve the 4-Queen problem. Unless it happens that choices made so far will be extended to a desired configuration, any algorithm to solve CSP have to backtrack so as to check other possibilities.

Here is a relevant excerpt from the article.

> Conversely, if it does not become possible to place a Queen at the pointed column, like in Fig. 5(c), **backtracker will backtrack** the previous assigned Queen’s column to reassign the conflicted Queen to a newly safe cell at the same column. Then, it will, at first, clear the constraints it created by calling the implemented modular function.
> 1 votes

---
Tags: algorithms, terminology, constraint-programming
---


# Question
Title: Union of infinitely many regular languages
I need to prove or disprove the following statement.

> If $A\_n ⊆ \Sigma^\*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits\_{n=0}^{\infty} A\_n$ is regular.

I know that if two languages are regular, then the union of the languages is also regular. I don't think that really applies to this problem, because it's the union of every $n \in \mathbb N$. Also, to help with my understanding with the definitions, is $A\_n$ a language or an alphabet, since it's a subset of $\Sigma^\*$?

# Answer
> 5 votes
> Is $A\_n$ a language or an alphabet, since it's a subset of $\Sigma^\*$?

A member of the alphabet, $\Sigma$ is called a symbol or a letter.
A member of $\Sigma^\*$ is called a string or a word, which is a finite sequence of symbols or letters.
A subset of $\Sigma^\*$ is called a language.

> If $A\_n\subseteq \Sigma^\*$ is regular for each $n\in\Bbb N$ then $\bigcup\limits\_{n=0}^{\infty} A\_n$ is regular.

As you suspected, this is not true. For example, let $A\_n=\\{a^nb^n\\}$. Then $\bigcup\limits\_{n=0}^{\infty} A\_n$ is the well-known non-regular language of words with equal number of $a$'s and $b$'s. Infinity should indeed be treated carefully.

---

**Exercise 1.** Give an example of a non-regular language $L$ over unary alphabet such that $L=\bigcup\limits\_{n=0}^{\infty} A\_n$ where $A\_n$ is a regular language for all $n$.

**Exercise 2.** Let $L$ be any language. Then $L=\bigcup\limits\_{n=0}^{\infty} A\_n$ for some regular language $A\_n$.

---
Tags: regular-languages, proof-techniques, sets
---


# Question
Title: Trying to understand the question(well spaced points ?) better
Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min\_{i,j \in S,i\ne j} |i-j|$ as large as possible. Come up an algorithm for fining the best S.

What is the correct output if the sorted array as 1, 2, 3, 4 ,5 ,6 and c is 3. What about if the sorted array as 1, 10, 11, 12, 23, 24, 25 and c is 3 ? also appreciated any hints to approached this question if you clearly understand what the question is asking.

# Answer
> What is the correct output if the sorted array as 1, 2, 3, 4 ,5 ,6 and C is 3?

Let us try. How about (1,2,3)? Too closely together. We should push away 3. (1,2,6) looks more far apart. Hmm, (1,2) is not good. (1, 3, 6) is the best.

> What about if the sorted array as 1, 10, 11, 12, 23, 24, 25 and C is 3 ?

We should include the smallest and biggest numbers, 1 and 25. Then we should choose a number as close to the middle as possible. (1,12,25).

...

Let us analyze $\min\_{i,j \in S,i\ne j} |i-j|$. Suppose $S=\\{a\_1, a\_2, \cdots, a\_C\\}$, where $a\_k\le a\_{k+1}$. Then $$\min\_{i,j \in S,i\ne j} |i-j|=\min\_{1\le k\lt C}|a\_{k+1}-a\_k|$$ since the difference between two non-adjacent numbers $a\_k$ and $a\_{k+t}$ must be greater than the difference between $a\_k$ and $a\_{k+1}$.

So the minimum difference among numbers in $S$ seems in "reverse proportion" to the difference between the adjacent or nearby numbers of the given array.

I will leave the above as a hint. Hopefully it is enough for you to figure out the rest.
> 1 votes

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


# Question
Title: What's a general rule for this little lambda calculus identity?
I've been fiddling around with a project that does some normalization of lambda calculus(-like) expressions and I stumbled upon that

```
(λ λ ... λ n (n-1) ... 2 1)

```

(De Brujin notation) is just the identity. I've generalized this a little to realize I can do stuff like

```
(λ λ λ λ 4 2 1) = (λ λ 2)

```

So basically if you can identify some character in your expression which is just the variable index *n*, and all variable indices to the left of that point are greater than *n*, and to the right is just descending down the variable indices one at a time to index *1* then you can eliminate all the indices to the right of that character (including that character) and then eliminate the \_λ\_s from the head of the expression and decrease the remaining indices appropriately.

This feels too haphazard to be the simplest form of this identity though. There must be a cleaner way to express this, and possibly a more general rule.

# Answer
Turns out this is just eta-reduction
> 2 votes

---
Tags: lambda-calculus
---


# Question
Title: Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b
How do I build a pushdown automata that accepts the language over the alphabet $\Sigma = \\{a, b\\}$, defined by the strings $w$, such that $|w|\_a = |w|\_b$?

I'm sorry I can't give any approach of what I did, but it's because I don't even know where to start with this ex. in particular. I tried to search anything on my books, but couldn't find nothing at all. Any suggestion is welcome.

# Answer
> 1 votes
The idea behind the construction is very simple: when the number of $a$'s and $b$'s read so far is equal, the stack will contain $\bot$. When $k$ more $a$'s were read, the stack will contain $\bot A^k$. When $\ell$ more $b$'s were read, it will contain $\bot B^\ell$.

Our automaton will accept by clearing the stack. We assume that the stack is initialized with $\bot$. The automaton has a single state and the following transitions:

* When reading $a$ and the top of the stack is $\bot$, replace it with $\bot A$.
* When reading $a$ and the top of the stack is $A$, replace it with $AA$.
* When reading $a$ and the top of the stack is $B$, replace it with $\epsilon$.
* When reading $b$ and the top of the stack is $\bot$, replace it with $\bot B$.
* When reading $b$ and the top of the stack is $B$, replace it with $BB$.
* When reading $b$ and the top of the stack is $A$, replace it with $\epsilon$.
* There is an $\epsilon$ transition which, when the top of the stack is $\bot$, replaces it with $\epsilon$.

The final transition is used when the input is exhausted, to conform with the acceptance condition of emptying the stack. If we want to use acceptance by final state, we need to add a new state which will be the only final state, and modify the last transition by transitioning into this state.

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


# Question
Title: Complexity of forming a min heap out of a given array with k inversions
If a given heap has $k$ inversions, what is the complexity of making it into a valid min heap? We could define an inversion as a tuple (node, descendant), where the node has a key value strictly higher than its descendant (all nodes have distinct key values).

This isn't an interview question, but is something that I thought of while learning about heaps. Searching for it on google gives zero hits.

Back when we learnt arrays and how to sort them, we were told that sorting arrays requires $\mathcal{O}(n + k)$ ($k$ = number of inversions) time complexity in insertion sort. I wonder if something similar exists for making a heap out of a given array.

I attempted to approach this problem in the following way. Assume a full binary tree (one with number of nodes equal to $2^h - 1$ ($h$ = height)). Note that we perform the sift down operation only when there exists an inversion. In the best case, the input array is already sorted so complexity is just order $n$, no sift downs are performed. In the worst case, input array is reverse sorted, so each internal node needs to be sifted down. That's summation of $\frac {(n + 1)}4 + \frac {(n + 1)}8\cdot2+\frac {(n + 1)}{16}\cdot3+\ldots= n-1$ siftdowns (solving it as a arithmetico geometric sequence) in the worst case, plus having to loop through the entire array .

In a more general case, I would say that we are visiting each node internal node once, performing a comparison with its children for cost $c$, and if it is out of place, perform a siftdown for additional cost $d$. If $i$-th internal node undergoes siftdown $k\_i$ times, then we can formulate the total complexity as:

$$=\sum\_{i=1}^{(n + 1) / 2}(c\cdot(k\_i+1) +d\cdot k\_i)$$

(as you always perform comparisons one more time than total number of siftdowns, except when you reach leaf node, which I approximated away)

This gives us:

$$=(c+d)k+\frac{(n+1)}2\cdot c$$

This suggests to me that that in worst case reverse sorted array, the order should be $n^2$, as the number of inversions $k$ is of that order. However, that we already know is not the case. Where is my analysis going wrong then?

# Answer
> 2 votes
We remove the inversions by beginning from the bottom (furthest level from the root) and going breadth-first up.

1. Start at the bottom level. We have a set of leaves, each satisfying the heap property.
2. Move one level up. If there is an inversion at this level, we fix it by sifting down. Now all sub-heaps from the bottom up to and including this level satisfy the heap property.
3. Continue applying 2. until finishing at the root level.

Suppose in the worst case that the $k$ inversions fill the top levels of a heap of height $h = \lfloor log(n) \rfloor + 1$. We have at most $\Sigma^{\lfloor log(k) \rfloor + 1}\_{i = 0} 2^i \cdot (h - (i + 1))$ swaps for sifting down, where $2^i$ represents the number of inversions at a given depth from the root. This is $O(n)$.

# Answer
> 1 votes
First of all, note that if we take a proper min-heap and look at it as an array, it could still have many inversions. The second part of the heap-sort algorithm is to convert this type of array into a sorted one (i.e. an array with 0 inversions). For example, a node in a min-heap can be larger than its sibling and the sibling's whole sub-tree. Therefore a good question that you can work on could be that what's the maximum number of inversions in a proper min-heap (Spoiler: you will find it to be quite large!). So in the process of making a min-heap, we do not eliminate all of the inversions necessarily. We might reduce or even increase that number (Can you find an example that a siftdown increases inversions?).

The other problem in your analysis is that changing the level (depth) of a node in a heap by 1 can reduce (or increase) the number of inversions by more than 1. In fact, this can change the number of inversions in relation to the number of nodes in that level (depth).

EDIT: Looks like I've misread your question. If we consider inversions to be tuples of nodes and descendants with the descendant bigger than the node, then the root can produce $n-1$ inversions, the nodes in the next layer can have inversions with all nodes in their subtrees and each produce $(n-3)/2$ inversions and so on. Therefore the number of inversions in the whole tree would be $T(n) = 2 T(\frac{n-1}{2})+n-1$, which is $O(nlogn)$.

# Answer
> 0 votes
Regardless of your analysis, the time taken to create a `min-heap` will always be linear i.e. $O(n)$. Inversions have no effect on this worst case complexity.

Imagine if you are given a problem where you have to convert a `max-heap` into a `min-heap`. In this case the inversions will be maximum in number, but this problem can be solved in linear time regardless of inversions. Why? Because we have to restore the heap property for all nodes in the heap. The leaf nodes already follow the heap property. The only nodes that might or might not are the internal nodes.

So if we restore heap property for the internal nodes then we are done and this can be done by heapifying the internal nodes one by one starting from the second last level from the bottom which takes linear time.

---
Tags: time-complexity, heaps
---


# Question
Title: Can maximum matching algorithms be used for maximum weight matching?
There are two fast algorithms for maximum matching on general graphs:

* Micali and Vazirani in $O(E\sqrt{V})$.
* Mucha and Sankowski in $O(V^{2.376})$.

Can these be also used for maximum weighted matching on general graphs? Note that Edmonds' Blossom algorithm can be used to solve both problems.

# Answer
> 5 votes
Ran Duan and Seth Pettie survey maximum matching algorithms in their 2014 paper Linear-Time Approximation for Maximum Weight Matching. In particular, Table III in their paper (page 5) lists algorithms for maximum weight matching in general graphs.

---
Tags: algorithms, matching
---


title: Truth table and logic circuit problem

text:
# Question
Title: Truth table and logic circuit problem
Does anyone know how to make this into a truth table and a logic circuit?

(x•y)+x

If so please send me the answer.

# Answer
Create a list of all possible (combinations) values for each of your variables, in this case, (x,y). See below for the headers. Remember a single variable can take either True or False.

X | Y | (X.Y) | (X.Y) + X

From them on you only need to carry out the operations outlined for each of those possible values: the dot is logical and the plus is the logical or.
> 0 votes

---
Tags: boolean-algebra
---


# Question
Title: Learning the activation function in a neural network?
Neural networks use specific activation functions, commonly used ones are tanh, ReLu.

I have seen that people have experimented with continuously parametrices activation functions, for instance here. Here, the additional parameter $\alpha$ which interpolates from logarithmus to linear to exponental, is optimized during the back-propagation step of the training.

I wonder whether much more general types of activation functions have been considered, such as Taylor-expansion of an unknown function where the coefficients are parameters in the training? It seems is a lot of degrees of freedom, that are not considered conventionally.

So my questions:

1. What is known about optimimality of actionation functions, apart from empirally testing? Are there mathematical proofs, for instance, that show some necessary properties for ideal learning (for instance, is monotonicity necessary, or could a sinusoidal activation function lead to optimal results too?)
2. If the answer to question 1 is no: Is there much research investigating the topic of learning activation functions?

# Answer
> -1 votes
Monotonicity is necessary! A neuron (perceptron) is either activated or not activated given an input. If you're trying to learn "red" and red should activate the neuron; the more red it's the most likely it should be activated (This monotonic gradient is what this activation function represents). If at certain redness it activates but at more redness it deactivates it makes no sense e.g. it can't learn red (The case for non-monotonic functions).

That they're differentiable functions makes it practical for the back propagation algorithm.

What they explain in your linked article is that they're trying to better approximate other functions e.g. sinusoidal. They're **not** trying sinuosoidal as an activation function. They're combining several monotonic functions to create yet another monotonic function, that is also differentiable.

---
Tags: neural-networks
---


# Question
Title: Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))
> Given a sorted array $A\[1,\ldots,n\]$ and element $x$ that located at position $k$. We know $x$, we don't know $k$. Write an algorithm that finds $k$, in $O(\min(\log k, \log(n-k))$ time complexity.

Any ideas how to solve this?

# Answer
> 4 votes
The basic idea, when we don't know $k$, is to *ask for elements with an exponentially growing index*. The most natural here is some use of powers of two. For example, we can ask for elements with indices $1$, $2$, $4$, $8$, $16$, $\dots$. Or with indices $1$, $3$, $7$, $15$, $31$, $\dots$. This way, it will take $O (\log k)$ steps to arrive at the first element greater than $x$.

After we found two boundaries for $k$, *do a regular binary search* between them. If we asked for consecutive powers of two, the length of the interval is also $O (k)$, and the binary search will complete in $O (\log k)$.

When we know that $n - k$ is small, *we can do the same but down from $n$*, instead of up from $1$. That is, first ask for elements at indices $n$, $n - 1$, $n - 3$, $n - 7$, $\dots$. Once we hit an element less than $x$, do a regular binary search between the boundaries we found.

Lastly, what to do when we don't know whether $k$ is small or $n - k$ is small, but want to complete using the fastest of the two? *Just run the searches in parallel.* That is, ask for element $1$, then $n$, then $2$, then $n - 1$, then $4$, then $n - 3$, and so on. Naturally, either an odd question gives us an element greater than $x$, or an even question gives us an element less than $x$, in $O (\log (\min (k, n - k)))$. Proceed then with the regular binary search.

# Answer
> 4 votes
Check the first element. Then check the last. Then the second, then the second to last, then the fourth, then the fourth to last, then the eighth, and so on. Stop upon bounding the location of x to a region at the front or back of the list.

Once you've bounded it you can just do a binary search.

Can you see why this works?

# Answer
> 2 votes
You can apply binary expanding search starting from both ends of the given array.

For ease of statement, I will assume $n=2^k$ for some integer $k\ge0$. Otherwise, a boundary check can be included in step 3.1. I will assume the given array is sorted from small to large; otherwise, one comparison between $a\_1$ and $a\_n$ can be done to find the sorting order and the procedure can be adjusted accordingly.

1. Check if $x=a\_1$ or $x=a\_n$. If yes, return 1 or $n$ accordingly and stop.
2. Let $i=1$.
3. Loop the following.
    1. Is $x\le a\_{2^i}$?
        * If yes, do a binary search for $x$ between $a\_{2^{i-1}}$ exclusively and $a\_{2^i}$ inclusively. Return the index and stop.
    2. Is $x\ge a\_{n-2^i+1}$?
        * If yes, do a binary search for $x$ between $a\_{n-2^{i}+1}$ inclusively and $a\_{n-2^{i-1}+1}$ exclusively. Return the index and stop.
    3. increase $i$ by 1.

---
Tags: algorithms, time-complexity, binary-search
---


# Question
Title: Decidability of equivalence to existential formulas
I'm looking for an algorithm to decide if a given first order formula over a fixed vocabulary admits a logically equivalent existential one (i.e. a formula in prenex form where all quantifiers are existentials).

Is it known if such an algorithm exists or does not exist? At least when no functions symbols are admitted? And if it actually exists, which is its complexity?

I know that, given a formula, we can build an equivalent one in prenex form. However, here is an example which illustrates that a formula, equivalent to an existential one, admits also an equivalent prenex formula which is not existential:

Consider the vocabulary $L=\\{E\\}$, where $E$ is a binary relation symbol. Then the formula $$\exists x\\,E(x,x)$$ which states that a directed graph admits a loop, is an existential formula and is equivalent to $$\exists x\forall y\\,\\,\\,\\,x=y\rightarrow E(x,y)$$ which is in prenex form, but not existential. So applying the algorithm to build a prenex form to the second formula would not produce an existential one.

# Answer
Surely, no such algorithm can exist in the general case: for a statement of the form $\forall x.\varphi$ statement in arithmetic, with $\varphi$ quantifier-free, there is a $\exists y.\psi$ statement such that

$$ \forall x.\varphi\ \Leftrightarrow \exists y.\psi$$

if and only if the statement is $\Delta\_0$, aka decidable. Because $\forall$ statements are undecidable in general, such an algorithm cannot exist.

---

**Edit:** The above reasoning is wrong! Indeed, the Bernays-Shönfinkel class of formulas includes the set of $\forall^\*\exists^\*$ formulas without function symbols (but with arbitrary relational symbols) and is decidable. The $\Delta\_0$ statements of arithmetic are not strictly speaking, quantifier free, but only contain *bounded* quantifiers (which are still quantifiers in FOL!)

**However**, this suggests an alternate proof: if there were a decision procedure which decides whether an arbitrary sentence were equivalent to some $\exists^\*$ sentence, then there would be a decision procedure for arbitrary (function-free) formulas as follows:

Given $\phi$ check whether it is equivalent to an existential formula $\psi$. If it is not, $\phi$ is not provable (otherwise it would be equivalent to the formula $\exists x.\top$).

If it is, then find such a $\psi$ (it's easy to show this is possible) and apply the decision procedure for the B-S class.

---

Finally, an exercise: repair the above proof using the undecidability of arithmetic.
> 1 votes

---
Tags: formal-languages, time-complexity, logic, first-order-logic
---


# Question
Title: Finding the frequency of each unique value of an attribute in a relation (RELATIONAL ALGEBRA)
I am trying to figure out how I can use aggregate functions to solve this problem. For example if I had the table

enrolled(student-id, course-id)
123 897
123 645
589 452
009 897

If I wanted to find the number of courses each student is enrolled in, how would I go about doing that? I was thinking of using the `count` function but I don't know how to separate each student-id

# Answer
In SQL: Use the GROUP BY and COUNT operators.
> 0 votes

---
Tags: database-theory, relational-algebra
---


title: Defining Local Search stopping criteria

text:
# Question
Title: Defining Local Search stopping criteria
When performing a local search, for example, a 2-node exchange in a metaheuristic (like GRASP), what is the usual stopping criteria for that procedure? Some bibliography says that the local search stops when no further improvement can be found in the neighboorhoud of the current solution. My question is: whether it is correct to stop the local search as immediately as a first better solution is found?

# Answer
> 0 votes
The stopping criterion depends on the specific algorithm used; some common ones include after a fixed number of iterations, or after the total improvement over the past $t$ iterations is at most $u$ (for some parameters $t,u$).

No, it's not correct to stop after you make the first improvement. Usually you will need many iterations of improvements.

---
Tags: algorithms, heuristics
---


# Question
Title: Checking the validity of a pyramid of dominoes
I came across this question in a coding interview and couldn't figure out a good solution.

You are given 6 dominoes. A domino has 2 halves each with a number of spots. You are building a 3-level pyramid of dominoes. The bottom level has 3 dominoes, the middle level has 2, and the top has 1.

The arrangement is such that each level is positioned over the center of the level below it. Here is a visual:

```
         [ 3 | 4 ]
    [ 2 | 3 ] [ 4 | 5 ]
[ 1 | 2 ][ 3 | 4 ][ 5 | 6 ]

```

The pyramid must be set up such that the number of spots on each domino half should be the same as the number on the half beneath it. This doesn't apply to neighboring dominoes on the same level.

Is it possible to build a pyramid from 6 dominoes in the arrangement described above? Dominoes can be freely arranged and rotated.

Write a function that takes an array of 12 ints (such that arr\[0\], arr\[1\] are the first domino, arr\[2\], arr\[3\] are the second domino, etc.) and return "YES" or "NO" if it is possible or not to create a pyramid with the given 6 dominoes.

Thank you.

# Answer
I can think of a brute force solution. Try all 6!\*(2^6) options. i.e. create all legal permutations of the pyramid and test each one if it holds the condition. It will take around 50K iterations to do.
> 1 votes

---
Tags: algorithms, data-structures, backtracking
---


# Question
Title: Topology vs sigma-algebra's as a framework for approximate information?
In the book "topology via logic" by Steven Vickers, topology is introduced for computer scientists, with the idea that topology captures the idea of approximate information.

I am somewhat confused by the explanation. In particular, I'm confused by how it relates to sigma-algebra's, which are also a way to express approximate information. In the case of sigma-algebra's, we can think of each set in the sigma-algebra as the sigma as a "signal" that we may receive, and the elements of that set as the "possible worlds" in which we would receive that signal. The sigma algebra then denotes the fact that we don't know in which exact world we are, but we know what subset of possible worlds we are. The axiom of closure under complementation follows intuitively from this: If we don't get the signal that we're in subset of worlds $A$ then we must be in $A^c$.

**What is the rationale behind using topology instead of sigma-algebra's for capturing approximate information in computer science?**

In particular, how are the differences between topology and sigma-algebra's imply for how they are used as frameworks for talking about approximate information?

* closure under complementation in sigma-algebra's but not in topology
* closure under countable unions in sigma-algebra but arbitrary unions in topology.
* closure under countable intersections in sigma-algebra but finite intersections in topology.

# Answer
> 4 votes
What sort of structure we get depends on what we are trying to model. Your starting assumptions may well lead to $\sigma$-algebras, but in computer science we have a certain understanding of "approximate information" which is naturally captured by topology.

Consider the following pieces of information:

* no information
* it is raining
* it is not raining

Clearly, "no information" approximates both "it is raining" and "it is not raining". If we think of "it is raining" as an observation that can be made, then the following assymetry is cruicial: having the information "it is not raining" is *not* equivalent to not having the information "it is raining". That is, if you *don't* receive some piece of information saying that $P$ holds, then you simply *don't know*. It is faulty to presume that you know $\lnot P$. This is the root cause of why the $\sigma$-algebra law of complementation is not valid in this context.

Now, to motivate closure under arbitrary unions and finite intersections (but not under arbitrary intersection), we need to take a slightly different point of view. Let us say that we want *verifiable information*, i.e., we say that we "have information $A$" if we can reasonably verify that $A$ holds.

1. To verify a binary conjunction $A \land B$, we verify *both* $A$ and $B$.
2. To verify an arbitrary disjunction $\bigvee\_i A\_i$ it is sufficient to verify a single $A\_j$.

However:

1. To verify an infinite conjunction $\bigwedge\_i A\_i$ we would have to verify all $A\_i$'s, and this may not be doable algorithmically (or in a physically realistic manner).
2. Just because we know how to verify $A$ does not mean that we also know how to verify $\lnot A$.

Example: to verify that a given machine $T$ halts it suffices to run the machine and wait until it stops. At this point we have verified that $T$ stops. (It is *irrelevant* what would have happened if $T$ did not stop!) But how could we verify that $T$ does *not* stop? It's not in general verifiable whether $T$ stops.

Another example: "$x \> 0$" is a verifiable property of computable reals, but "$x \leq 0$" is not. (Recall that $x \in \mathbb{R}$ is *computable* if there is an algorithm which, for any given $n \in \mathbb{N}$ gives an interval $\[a\_n,b\_n\]$ with rational endpoints such that $a\_n \< x \< b\_n$ and $b\_n - a\_n \< 2^{-n}$.) The verification algorithm works as follows: given an algorithm for computing $x$, find $n \in \mathbb{N}$ such that $0 \< a\_n$. If $x \> 0$ then this algorithm will terminate after a finite time, thereby confirm that $x \> 0$. If $x \leq 0$ then the algorithm will run forever, but that is OK because we only need to confirm $x \> 0$, we are not trying to *deny* $x \> 0$ in case it does not hold. In contrast, we cannot confirm $x \leq 0$ because there is no algorithm which takes as input $x \in \mathbb{R}$ and terminates if, and only if, $x \leq 0$.

# Answer
> 2 votes
I don't consider myself knowledgable enough about logic to provide a complete answer myself, but I think the following two posts (1 from math.stackexchange, one from mathoverflow) contain some information that may help you understand the topology part of your question better:

1. Dan Piponi's answer here gives a good explanation about how topologies can represent approximate information
2. This post which was written later summarizes the first post + has some additional information about the information-interpretation of topologies

Unfortunately I'm not familiar with corresponding explanations for Sigma Algebras, even though I think your question is quite natural and agree that both objects are somewhat similar.

---
Tags: logic, topology
---


title: Complexity of sending an $n$-bit string

text:
# Question
Title: Complexity of sending an $n$-bit string
Consider a $2$-party communication model in which $A$ wish to send to $B$ an $n$-bit string. It is very easy to prove that any deterministic protocol for this problem requires $\Omega(n)$ bits to be transmitted. It is also well-known that any randomized protocol for this problem also requires $\Omega(n)$ bits to be transmitted. Although this considered to be a trivial fact, I failed to formally prove (or find a formal proof) for this. So my question is: how to show that any randomized protocol for this problem requires $\Omega(n)$ bits to be transmitted?

# Answer
You haven't defined when a randomized protocol is declared to be successful, so I will assume that at the end of the protocol, Bob tells a judge what he thinks the message is, and we want that for each message $x$, the probability that Bob is correct is at least $1-\epsilon$.

Let $X$ be a random $n$-bit string, and let $\Pi$ be the corresponding transcript. Let $R$ be the randomness in the protocol (i.e., given $R$ the protocol is deterministic, and Bob's output is deterministic). Let $Y$ be Bob's output, and let $B$ be an indicator variable for the event $X=Y$.

The definition of correctness of the protocol shows that $$ \begin{align\*} H(X|\Pi R) &\leq H(BX|\Pi R) \\ &= H(B|\Pi R) + H(X|\Pi RB) \\ &\leq 1 + \Pr\[B=1\] H(X|\Pi R,B=1) + \Pr\[B=0\] H(X|\Pi R,B=0) \\ &\leq 1 + 1 \cdot 0 + \epsilon \cdot n \\ &= \epsilon n + 1. \end{align\*} $$ This implies that $$ H(\Pi|R) = H(X\Pi|R) - H(X|\Pi R) = H(X) - H(X|\Pi R) \geq (1-\epsilon) n - 1, $$ since $H(X\Pi | R) = H(X | R)$ (given $R$, Alice's input $X$ determines the transcript $\Pi$) and $H(X|R) = H(X)$ (since Alice's input and the randomness are independent).

We conclude that the communication complexity is at least $$ (1-\epsilon) n - 1 = \Omega(n). $$
> 1 votes

---
Tags: algorithms, communication-protocols, communication-complexity
---


# Question
Title: Why integer division is of equal complexity as multiplication
I am trying to understand the fact that integer division is no more difficult than integer multiplication. I found some references - here and this lecture note. Wikipedia says if there is a way to multiply integers in time M(n), then we can divide them in CM(n). When I think of division a/b as finding integers d and r such that a = bd + r, then this above fact somehow aligns with my intuition. But I could not find any way to mathematically prove this. Although the lecture note has proof, but I am not able to understand. Can anybody please give me a simple mathematical proof or any idea how to do it?

# Answer
The wikipedia page suggests using Newton-Raphson Division to get $O(M(n))$.

The way Newton-Raphson Division works is by finding the solution $x$ of $\frac{1}{x}-b=0$ (so that $x=1/b$), and then returning $ax$.

A Newton-Raphson iteration in general is

$$ x\_{i+1} = x\_i - \frac{f(x\_i)}{f'(x\_i)}. $$

In this case $f(x)=\frac{1}{x}-b$ and $f'(x)=\frac{-1}{x^2}$, so the iteration works out to

$$ x\_{i+1} = x\_i(2-bx\_i), $$ which takes 2 multiplications per iteration.

Given a good enough starting guess, $x\_0$, Newton-Raphson is guaranteed to double the number of accurate bits per iteration, so needs to be run for $O(\log n)$ iterations for $n$ bits of accuracy.

All of the above is for real $x$. To make it work for integers the trick is to actually calculate $x=\frac{2^n}{b}$ instead of $x=\frac{1}{b}$, which (with a little bit of "normalization") lets you do all the arithmetic with integer multiplies, subtracts, and shifts.

And now how you do it in the same time as multiplication:

Say you want a 1024 bit result, and you have 16 correct bits.

You do one iteration step with 32 bit precision, getting a 32 bit result. Then you do an iteration with 64 bit precision, then 128 bits, then 256 bits, then 512, then 1024.

So the cost isn’t M(n) every time, it’s M(n/64), M(n/32), ..., M(n/2), M(n). Adding up to 2M(n).
> 6 votes

---
Tags: algorithms, complexity-theory, asymptotics, arithmetic
---


title: Why is EXACT-CLIQUE not in co-NP?

text:
# Question
Title: Why is EXACT-CLIQUE not in co-NP?
In my lecture I saw the problem of $\text{EXACT-CLIQUE} = \\{\langle G,k\rangle : \text{the largest clique in $G$ is of order $k$}\\}$

I understand this problem is obviously not in NP as we would need to check all cliques, but if we consider the complement of the problem, (i.e. is the largest clique not of order $k$), wouldn't this be in NP? Because we could simply use non-determinism to guess a clique bigger than $k$ and then check if it indeed makes a clique. My lecturer said however that the problem is not in co-NP but I did not understand the explanation.

# Answer
> 2 votes
The problem "Does the largest clique have a size ≤ k" is in co-NP - if the answer is NO then there is a clique of size \> k, and guessing that clique proves that the answer is NO.

But the problem here is "Does the largest clique have a size of exactly k". If the answer is NO then it could be that the largest clique has size k-1 and there are no cliques of size k, k+1, k+2 etc. Sure, you could guess a clique of size k-1 - but that doesn't prove a clique of size k doesn't exist. And you can't guess a clique of size k+1 because no such clique exists.

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


# Question
Title: How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
$L = \\{x \in(a,b,c,d)^\* \mid -10 \leq ( |x|\_a + |x|\_b) - ( |x|\_c + |x|\_d) \leq 10 \\}$

I don't have any idea. Can someone help me.

# Answer
> 0 votes
If anyone would be interested, here is my pda to $L = \\{x \in(a,b,c,d)^\* \mid -1 \leq ( |x|\_a + |x|\_b) - ( |x|\_c + |x|\_d) \leq 1 \\}$

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


# Question
Title: Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?
I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that gives rise to meaningful $L\cap L^2$.

Any hint would be appreciated!

# Answer
> 3 votes
You can take $$ L = \\{ a^n b^n : n \geq 1 \\} \cup \\{ a^k b^n a^n b^\ell : n,k,\ell \geq 1 \\}. $$ You can check that $$ L \cap L^2 = \\{ a^n b^n a^n b^n : n \geq 1 \\}. $$

# Answer
> 2 votes
The intersection of the form $L\cap L^2$ actually turns out to be quite powerful. In fact languages like this can code Turing machine computations.

Let $L\_1, L\_2 \subseteq\\{a,b\\}^\*$ and let $\\#$ be a third "special" symbol. Consider $L = L\_1\\# \cup L\_2\\#\\#$. The only strings in $L\cap L^2$ must end in $\\#\\#$, and before that must be a string in $L\_1\cap L\_2$.

Now one can do weird things indeed. Let $L = \\{a^nb^{2n}\mid n\ge 1\\}^\*a^\*\\# \cup a^1\\{b^na^n\\}^\*\\#\\#$. Then $L\cap L^2$ consists of strings of the form $a^1b^2a^2b^4a^4\dots b^{2^k}a^{2^k}\\#\\#$.

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


# Question
Title: Proving that no 2-state DFA decides the language A = {x ∈ {0, 1}* | bnum(x) is divisible by 3}
I am doing a problem where I need to prove that no 2-state DFA decides the language A = {x ∈ {0, 1}\*| bnum(x) is divisible by 3}.

It's seems pretty obvious at first, because aren't there only 4 DFA's with two states that define it? Also, since x is divisible by 3, the DFA would need to have 3 states to define the remainder values.

So I feel like I have a good understanding of the problem, but how do I more formally prove the statement? Any help is appreciated.

# Answer
> 2 votes
Remainder values is indeed the clue! Obviously the strings $1$ and $10$ cannot end in a final state as they represent number `1` and `2` respectively. But can they end in the same state?

---
Tags: finite-automata
---


# Question
Title: Prove the MinAveCodeLen of a product information source is less than the sum of that of the multiplicand and multiplier source?
The product of 2 independent sources $(S\_A,P\_A)$ and $(S\_B,P\_B)$ is defined as

$$ (S,P)\text{ s.t. }S = \\{s\_As\_B|s\_A\in S\_A,s\_B\in B\\}\text{ and }\ P(s\_As\_B) = P\_A(s\_A)\cdot P\_B(s\_B)\\,\forall s\_A\in S\_A,s\_B\in S\_B $$

and the MinAveCodeLen is the minimum average codeword length which is equal to the average codeword length of a Huffman coding.

The problem is to prove

$$ \mathrm{MinAveCodeLen}(P)\leq\mathrm{MinAveCodeLen}(P\_A)+\mathrm{MinAveCodeLen}(P\_B) $$

The original problem is quite confusing. I am asked to prove $H(P\_A)+H(P\_B)=H(P)$ in the previous part, so I was trying to relate the problem with $H$ at first with no progress.

# Answer
> 2 votes
It's so wired that again, I'm answering my own question... I have to admit I am not confident at all when confronted with constructive proof problems.

An encoding scheme for ${P}$ could be described graphically as follows: Suppose $T\_A$, $T\_B$ are 2 Huffman trees for ${P}\_A$ and ${P}\_B$ respectively. For each leaf $s\_{Ai}$ in $T\_A$ replace it with $T\_B$, i.e.  Letting $|S\_A| = q,|S\_B| = q$, the average code word length of this coding scheme is $$C = \frac{\sum l\_{Ai}+l\_{Bj}}{pq} = \frac{q\sum l\_{Ai}+p\sum l\_{Bj}}{pq} = \mathrm{MinAveCodeLen}({P}\_A)+\mathrm{MinAveCodeLen}\mathbb{P}\_B)$$ where $l\_{Ai}$, $l\_{Bj}$ are the codeword length of $s\_{Ai}$ and $s\_{Bj}$ in the Huffman code corresponding to $T\_A$, $T\_B$. Therefore, $$\mathrm{MinAveCodeLen}({P})\leq C\leq\mathrm{MinAveCodeLen}({P}\_A)+\mathrm{MinAveCodeLen}({P}\_B)$$

---
Tags: information-theory, coding-theory, encoding-scheme, huffman-coding
---


# Question
Title: Why is every finite language A ⊆ Σ* regular
So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ\* are regular? Is there a formal proof of it or is it just because a DFA can represent any finite language since the states would be finite as well?

# Answer
The proof goes something like this:

* If $A$ is a finite language, then it contains a finite number of strings $a\_0, a\_1, \cdots , a\_n$.
* The language $\\{a\_i\\}$ consisting of a single literal string $a\_i$ is regular.
* The union of a finite number of regular languages is also regular.
* Therefore, $A = \\{a\_0\\} \cup \\{a\_1\\} \cup \cdots \cup \\{a\_n\\}$ is regular.
> 14 votes

# Answer
There is also a direct proof. Let $P$ be the set of all prefixes of words in $A$. Since $A$ is finite, so is $P$. We construct a DFA whose states are $\\{ q\_p : p \in P \\} \cup \\{ q' \\}$. The initial state is $q\_\epsilon$. A state $q\_p$ is final if and only if $p \in A$. When at state $q\_p$ and reading $\sigma$, if $p\sigma \in P$ then we move to $q\_{p\sigma}$, otherwise we move to $q'$. When at state $q'$, we always stay in $q'$.

What I described above is the minimal DFA. You can get a somewhat simpler DFA by taking an arbitrary superset of $P$, such as the set of all words of length at most $n$, where $n$ is the length of the longest word in $A$.
> 4 votes

---
Tags: regular-languages, finite-automata
---


# Question
Title: Proving a set is at a certain level of the arithmetical hierarchy
I'm interested in methods for proving a set is at some level $\Sigma^0\_n$ (or $\Pi^0\_n$) in the arithmetical hierarchy, and in particular, proving it is at the level with the smallest $n$ possible.

I know that a set is in $\Sigma\_n^0$ if it can be expressed as a sequence of $n$ quantifiers (starting with $\exists$ and then switching between $\exists$ and $\forall$) on variables, followed by a decidable formula on those variables. I also know membership in $\Pi\_n^0$ can be proved in a similar way, just starting with $\forall$ instead of $\exists$.

These slides use that approach to place several sets at different places in the arithmetic heirarchy (on slides 26,31,33, and 35, for example).

Here's where things start to get tricky for me. If a language is in $\Sigma^0\_n$, it seems like it's also trivially in $\Sigma^0\_{n+1}$, $\Sigma^0\_{n+2}$, and so on -- because you can take the formula you used to show that the language was in $\Sigma^0\_n$, and tack on "dummy" quantifiers that don't actually do anything.

So, let's say I want to proving that a language is in $\Sigma^0\_n$, but *not* $\Sigma^0\_{n-1}$, i.e. I want to put the language in its lowest spot on the arithmetical heirarchy. Now, it seems like just showing that the language corresponds to a a $\exists,\forall,...$ sequence followed by a decidable formula won't cut it, because there's a chance that I was adding useless quantifiers to artificially inflate my language's difficulty. What techniques exist to get around this issue -- How do I prove that my quantifiers are "essential", so to speak?

I'm definitely interested in being as formal as possible with such a proof, so any links to textbooks or papers would be much appreciated.

# Answer
In order to show that a language is in (say) $\Sigma\_n^0$ but not in $\Sigma\_{n-1}^0$ or $\Pi\_{n-1}^0$, we show that the language is *complete* for $\Sigma\_n^0$. Since the arithmetical hierarchy is strict (by a generalization of the proof of the uncomputability of the halting problem by diagonalization, which you can find in many different sources), a $\Sigma\_n^0$-complete language cannot be in any lower level of the hierarchy.

How do we show that a language is complete for a level of the hierarchy? Either by a *direct* proof or by *reduction*. Let me illustrate both techniques using variants of the halting problem.

We will consider two variants of the halting problem:

* $H\_1$ consists of all pairs $(\langle M \rangle, x)$ such that $M$ is a Turing machine halting on $x$.
* $H\_2$ consists of all singletons $\langle M \rangle$ such that $M$ is a Turing machine halting on an empty tape.

Let us show that $H\_1$ is $\Sigma\_1^0$-complete by a direct proof. In order to show that it is in $\Sigma\_1^0$, we notice that $(\langle M \rangle,x)$ iff there exists $t$ such that $M$ halts on $x$ within $t$ steps; the latter predicate is computable.

In order to show that $H\_1$ is $\Sigma\_1^0$-hard, consider any language $L \in \Sigma\_1^0$. By definition, there exists a computable predicate $P$ such that $$ x \in L \Longleftrightarrow \exists y \\, P(x,y). $$ Let $M$ be a Turing machine that on input $x$, enumerates all strings $y$ (say first by length, then lexicographically), for each one computes $P(x,y)$, and halts if $P(x,y)$ holds for any $y$. Then $x \in L$ iff $(\langle M \rangle, x) \in H\_1$. The mapping $x \mapsto (\langle M \rangle, x)$ is clearly computable, and so this reduces $L$ to $H\_1$.

We now show that $H\_2$ is $\Sigma\_1^0$-complete by reduction from $H\_1$. Given an instance $(\langle M \rangle, x)$, we construct (in a computable way) a new machine $M\_x$ that first initializes the tape $x$, and then transfers control to $M$. Clearly $(\langle M \rangle, x) \in H\_1$ iff $\langle M\_x \rangle \in H\_2$. Since the reduction is computable and $H\_1$ is $\Sigma\_1^0$-hard, this shows that $H\_2$ is also $\Sigma\_1^0$-hard. Also, $H\_2 \in \Sigma\_1^0$, using the same proof as above. So $H\_2$ is $\Sigma\_1^0$-complete.
> 6 votes

---
Tags: complexity-theory, computability
---


# Question
Title: Can generalized Turing machines compute all reals?
Super-recursive algorithms are theoretical super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines.

In this entry it is said:

> A symbol sequence is computable in the limit if there is a finite, possibly non-halting program on a universal Turing machine that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π but still excludes most of the real numbers, because most cannot be described by a finite program. Traditional Turing machines with a write-only output tape cannot edit their previous outputs; generalized Turing machines, according to Jürgen Schmidhuber, can edit their output tape as well as their work tape

Does that mean that, theoretically, generalized Turing machines, cannot compute all reals? Can generalized Turing machines do (fully) hypercomputation (theoretically)?

(I know that there is strong evidence against hypercomputation. I'm asking this only from a theoretical perspective)

# Answer
> 9 votes
Any machine model in which a machine can be described by a string over a fixed alphabet can only compute countably many things. Since there are uncountably many real numbers, all of these machine models fail to compute almost all real numbers.

In fact, the alphabet need not be fixed. It is enough that the alphabet is taken from some countable set of finite alphabets, for example $\\{1,\ldots,n\\}$ for every $n$.

---
Tags: turing-machines, computability, real-numbers, hypercomputation
---


# Question
Title: How to minimize this DFA with already merged states?
The original nondeterministic FSA I have is:

After converting this to a DFA I get:

If I use the Myhill-Nerode theorem on the current DFA, I get all pairs marked, so this is already minimized. But I think this is incorrect.

I want to minimize this DFA. How should I do this using the Myhill-Nerode theorem, since some of the states are merged already?

# Answer
> 1 votes
After inputs $\epsilon$, $a$, $ab$, $abc$, $abca$ we must be in five different states because appending $b$ to one of these leads to an accept only for $abca$, appending nothing to any of the others leads to an accept only for $abc$, appending $c$ leads to an accept only for $ab$, appending $bc$ to any of the remaining only for $a$.

A bit more formally, given a string $\alpha$, we note in a 4-tuple whether $\alpha$, $\alpha b$, $\alpha c$, $\alpha bc$ are accepted. For $\alpha = \epsilon, a,ab,abc,abca$, these 4-tuples are $(0,0,0,0)$, $(0,0,0,1)$, $(0,0,1,0)$, $(1,0,0,0)$, $(1,0,0,1)$, hence all distintc. This is only possible if these $\alpha$ correspond to differnt states.

---
Tags: finite-automata
---


# Question
Title: Language of all sequences of permutations whose product is the identity
Let $\Sigma$ be the set of all permutations in $S\_n$. What is the minimum number of states in a DFA accepting the language of all words over $\Sigma$ which multiply to the identity permutation?

For example, if $n=2$, then $\Sigma$ consists of two mappings, the identity mapping $\iota$ and the transposition $\tau$. The language in this case consists of all words containing an even number of $\tau$'s.

# Answer
You haven't stated what happens to the empty word – I'm assuming it's accepted.

It is easy to check that the equivalence classes of the Myhill–Nerode relation correspond to all words multiplying to a certain permutation. Therefore the minimal DFA contains $n!$ states.

If the empty word is not allowed, there are $n!+1$ equivalence classes, one of them consisting only of $\epsilon$.
> 1 votes

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


# Question
Title: What is an example of a weakly universal hash function that is not pairwise independent?
A family of hash functions $H\_w$ is said to be *weakly universal* if for all $x \ne y$ :

$$P\_{h \in H\_w}(h(x) = h(y)) \leq 1/m$$

Here the function $h:U \rightarrow \[m\]$ is chosen uniformly from the family $H$ and we assume $|U| \> m$.

A family of hash functions $H\_s$ is said to be *strongly universal* if for all $x \ne y$ and $k, \ell \in \[m\]$:

$$P\_{h \in H\_s}(h(x) = k \land h(y) = \ell) = 1/m^2$$

What is a concrete example of a hash function family which is weakly universal but not strongly universal?

# Answer
> 5 votes
Let $U = \[m\]$, and let $h$ be the identity function.

If you insist that $|U| \> m$, then you can take $U = \[m+1\]$, and consider the functions $h\_i$, for $i \in \[m\]$, given by $$ h\_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i & \text{if } x = m+1. \end{cases} $$ The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.

---
Tags: hash, hash-tables, probabilistic-algorithms
---


# Question
Title: Name of a tree with arbitrary number of branches at each fork point?
A binary tree is a rooted tree with the root having an indegree of 0 and all other nodes of 1. The outdegree is 0, 1 or 2 for all nodes.

How do you call a rooted tree if the **number of branches per node is arbitrary** (outdegree of *n*) but the indegree 1 for all nodes other than the root node?

# Answer
> 3 votes
## Rooted Tree

> How do you call a rooted tree if the number of branches per node is arbitrary (outdegree of n) but the indegree 1 for all nodes other than the root node?

That is none other than an rooted tree itself or, more accurately, an arborescence or branching tree or out-tree according to the following quote from Wikipedia entry on rooted tree.

> A rooted tree is a tree in which one vertex has been designated the root. The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. When a directed rooted tree has an orientation away from the root, it is called an arborescence, branching, or out-tree; when it has an orientation towards the root, it is called an anti-arborescence or in-tree.

## Multitree

Your are also interested in what you might call "Poly-hierarchical rooted graph".

> An arbitrary rooted tree could also be a poly-hierarchy as far as I understand, with some nodes having an indegree \> 1 i.e. multiple parents.

However, since every vertex other than the root has a single parent in a rooted tree by definition, it is not a viable idea to call them "Poly-hierarchical rooted tree". The conventional name for them is multitree as illustrated below, thanks to Wikipedia.

> A multitree may describe either of two equivalent structures: a directed acyclic graph in which the set of nodes reachable from any node form a tree, or a partially ordered set that does not have four items $a$, $b$, $c$, and $d$ forming a diamond suborder with $a\le b \le d$ and $a\le c \le d$ but with $b$ and $c$ incomparable to each other (also called a diamond-free poset).

## Polytree

You might be interested in polytree, as illustrated below, thanks to Wikipedia again. It is "also known as oriented tree or singly connected network". It is "a directed acyclic graph whose underlying undirected graph is a tree."

## Hasse Diagram

Another related concept is Hasse diagram, which is "used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction", as illustrated below.

---

**Exercise 1**. Draw a polytree that is not a rooted tree. Draw a multitree that is not a polytree. Draw a Hasse diagram that is not a multitree.

**Exercise 2**. Every rooted tree is a polytree. Show that every polytree is a multitree. Show that every multitree is the Hasse diagram of some finite partially ordered set.

---
Tags: graphs, terminology
---


# Question
Title: Is the infinite language unrecognizable in a Turing machine?
This question is building up on an older one, here.

But now let's say we keep $Σ=\\{0,1\\}$. Is the TM that accept anys ($1^x \mid x \gt 0$) recognizable?
That means 1, 11, 11111, 1111111, and so on are all accepted.

I believe the TM is unrecognizable. This is because for it to be recognizable, we would have to halt. Yet, with no upper limit, we can have $1^\infty$ \- meaning we will never halt. Does this work?

The above was an example of a language, didn't think it would be recognizable. A better way to phrase my question is: Is there a language of any number of $1$s over $\Sigma=\\{0, 1\\}$ that you can make unrecognizable?

# Answer
> 21 votes
I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the *language* $\\{1^x \mid x \in \mathbb{N}\\}$ is recognizable.

A language is recognizable if and only if we can build a Turing machine that accepts every string in the language, and does not accept any string not in the language. And we can indeed build a Turing machine that does this!

```
Algorithm:
    Check the number under the head.
    If it's 0, fail.
    If it's the end of the string, accept.
    If it's 1, move to the right and repeat.

```

The key is, while there's no upper limit, $x$ has to be a natural number—*and $\infty$ is not a natural number*. In other words, while $x$ can be arbitrarily large, it has to have some finite value. It can't actually *be* $\infty$.

# Answer
> 6 votes
Languages are sets of finite strings. Every input to a Turing machine is a finite string. $1^\infty$ is a thing, but not in this model of computation (and usually we're more specific about what infinity we're talking about).

# Answer
> 1 votes
A few answers has addressed the confusion about the length of a word being infinite.

Here I would like to address the following question.

> A better way to phrase my question is: Is there a language of any number of 1s over $\Sigma=\\{0,1\\}$ that you can make unrecognizable?

Note that if a language of any number of 1s is unrecognizable, then it is unrecognizable over any alphabet that contains 1.

That question has been answered positively here. I would like to add another famous "constructive" example, **busy beaver sequence**, a.k.a. **Rado's sigma function**. Let $\sigma:\Bbb N\to\Bbb N$ be that function. We know that $$\sigma(0)=0,\ \sigma(1)=1,\ \sigma(2)=4,\ \sigma(3)=6,\ \sigma(4)=13, \\\sigma(5)\ge4098,\ \sigma(6)\ge 1.29\*10^{865},\cdots. $$

We have not determine $\sigma(5)$ yet!

The language for $\sigma$ is $$\\{1^{\sigma(n)}: n\in \Bbb N\\}=\\{\epsilon, 1, 1111, 111111, 1111111111111, \cdots\\},$$ which is undecidable.

# Answer
> 0 votes
$1^\infty$ is not an actual word in the language, since $\infty$ is not a natural number - even though the language contains infinitely many words, each word has a finite, arbitrarily large length $n$.

A language is decidable if there is a Turing Machine can decide it in a finite number of steps for each input. That's obviously true here - there is no word that will take infinitely long to process.

> The above was an example of a language, didn't think it would be recognizable. A better way to phrase my question is: Is there a language of any number of 1s over $Σ=\\{0,1\\}$ that you can make unrecognizable?

You mean an undecidable unary (consisting only of one symbol) language? Sure there is!

Take any language $L \in \\{0,1\\}^\*$ that you already know to be undecidable. (For example, a language that encodes all halting Turing Machines.) Modify it a bit by adding "1" to the start of each word, to keep leading zeros.

Then let your language $L'$ consist of the word $1^n$ for every $n$ whose binary representation is in $L$. ~~As each word in $L$ can be easily turned into a word in $L'$~~\*, a machine that decides $L'$ could be used to decide $L$. As $L$ is undecidable, so is $L'$.

Edit: \*To be more precise: "As each binary word $w$ beginning with 1 can be converted into a word consisting of 1s $w'$ such that $w\in L$ iff $w' \in L'$..."

---
Tags: formal-languages, turing-machines, automata, undecidability
---


# Question
Title: Is determining if a Turing machine runs in constant time decidable if one assumes it halts?
As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts?

The decision problem, more formally:

Given a Turing machine $M$ where it is assumed it halts on all inputs, determine if it runs in $O(1)$ time.

Is this decidable?

# Answer
> 2 votes
This answer is for the following version of the question:

> Can we decide whether an algorithm runs in constant time (that is, within $N$ steps, for some $N$), given that it is guaranteed to always halt?

This is not decidable. Given a Turing machine $T$, construct a new Turing machine $M$ which on input $t$ runs $T$ for up to $t$ steps. Then $M$ runs in constant time iff $T$ halts.

# Answer
> 1 votes
It is still undecidable. Pick some algorithm M that has a time complexity dependent on the input (whatever exactly that means).

Now given some Turing machine T, consider the algorithm A that works as follows:

1) Simulate T on empty input until it halts. 2) Run M on the original input.

If T does not halt, then A never halts for any input, hence has time complexity independent of the input. If T halts after k steps, then A essentially takes k steps more than M does for any input. Since M's time complexity depends on the input, so should the time complexity of A.

---
Tags: computability, time-complexity, undecidability, halting-problem
---


# Question
Title: How broad is the meaning of "algorithm"?
This is a purely terminological question.

The word algorithm, as I have learnt it refers to something like an "effective method, a sequence of steps, for doing something". There are alternative statements giving roughly the same idea.

But for some computer systems, such as neural networks, it is somewhat stretching it (for me) to say that they are "algorithms". e.g. neural networks are very "approximate" compared to traditional software algorithms.

* Would people in general say that a particular neural network with a particular parameterization (i.e. not the learning algorithm, but the resulting neural net itself) is an "algorithm")?
* If not, what other word is there to refer to the more general class that contains such networks as well?

# Answer
No. A specific neural network is just the (weights) parameters of an algorithm for function approximation.

A neural network in general yes, is the algorithm for classifying a given x into a class, given a probabilistic distribution (weights).

This is like asking weather a specific VAT rate is an algorithm. The calculation of VAT is an algorithm but the VAT rate is not.
> 2 votes

# Answer
A neural network itself is more of a *data structure* than an algorithm; it has a set of numbers and functions and specific connections between them, similar to a graph. You could define algorithms which use a neural network such as: do a convolution on my image using the first layer of weights, then apply the first non-linearity, then ..., then return the class with the largest softmax probability as the class of this image. That's an algorithm for classifying an input with a given neural network. There are other algorithms that use neural networks too like those for learning their weights, using them to play games, etc. These are sometimes randomized algorithms (due to randomness in the initialization of the weights and in permuting the training data, as well as often random augmentations of the training data). Graphs, similarly, have many associated algorithms (finding paths, minimum cuts, etc.).

As you said, I'd think of an algorithm as a set of steps or instructions for completing some task. Generally when we think of algorithms, that task is well-specified: given a list of numbers, I want to output them in order from smallest to largest. Then we can construct algorithms for which we provide guarantees (proofs) that they will always complete this task. We can also give proofs showing, e.g., how long our algorithms will take (asymptotically) for an input of a given size.

When you think about the algorithm which takes as inputs a neural network and an input to the network and outputs a label for the input, the steps themselves are well-defined, but the task might be trickier to define. You might like to say, I want an algorithm which will provably always give me the correct label, just like my sorting algorithm always orders my lists properly. There has been a lot of research recently about how well the algorithms used to train neural networks converge to weights which minimize the training loss, but you have to start making some assumptions if you want to say something about how well using a prediction algorithm with the network generalizes to datapoints never seen in training. Generally, we can't say that using a given neural network gives any specific approximation-factor to an optimal algorithm.

So, I would say that there is an *algorithm* for making predictions using a neural network, but the only thing I can be sure of about the task that algorithm is accomplishing is that, e.g., if I'm doing a $k$-way classification, the result I get will be one of the $k$ classes (or, for regression, the output will be some real number).
> 2 votes

---
Tags: algorithms, terminology, neural-networks
---


# Question
Title: How to convert this DFA with multiple final states to a regular expression? (State elimination method)
So I have a DFA which I would like to convert to a regular expression. As you can see it has multiple accepting states and the start state has incoming input 'a' from q2 and 'b' from q4.

I want to convert this into a regular expression using State elimination, and I know that I need to first create a new state call it 's' which replaces q0 as the start state, and then create another new state (call it 'f') which will be the new final state, and make q1, q2, q3, and q4 non-accepting states, and make epsilon transitions from the former accepting states to the new final state.

My question is, when I eliminate say q1, I don't know what the regular expression will be as a result. Now since q1 has 2 outgoing transitions 'a' to a2 and epsilon to f, what would be that regular expression? I know that for q2 it would be a(ba)*a(ba)* ... then q0 to f will be a(ba)\*.. so far it doesn't make sense to me how this will end up becoming the correct regular expression. Am I on the right track?

# Answer
> 1 votes
> When I eliminate say $q\_1$, ..., now since $q\_1$ has 2 outgoing transitions, '$a$' to $q\_2$ and $\epsilon$ to $f$, what would be that regular expression?

Here are the transitions among the neighbors of $q\_1$, which are $q\_0, q\_2$ and $f$ when $q\_1$ is eliminated.

* $\delta(q\_0, ab)=q\_0$
* $\delta(q\_0, aa)=q\_2$
* $\delta(q\_0, a)=f$
* $\delta(q\_2, a+bb)=q\_0$
* $\delta(q\_2, ba)=q\_2$
* $\delta(q\_2, \epsilon+b)=f$

> $a(ba)^\* + a(ba)^\*a(ba)^\*(aa(ba)^\*a(ba)^\*)^\* + b(ab)^\* + b(ab)^\*b(ab)^\*(bb(ab)^\*b(ab)^\*)\*$

I am afraid the above is not correct since it does not include $abbaa$ nor $abbab$

# Answer
> -2 votes
My final answer was:

a(ba)\* + a(ba)\*a(ba)\*(aa(ba)\*a(ba)\*)\* + b(ab)\* + b(ab)\*b(ab)\*(bb(ab)\*b(ab)\*)\*

Just checking if it's right

---
Tags: finite-automata
---


# Question
Title: How is adversarial autoencoder better than an ordinary autoencoder?
An adversarial autoencoder helps us to impose a prior distribution $p(z)$ on the encoded values of the inputs, or $q(z)$.

On the contrary, an ordinary autoencoder (which we train like an ordinary neural network (comparing output to input using mean squared error) does not give us any control over the encoded distribution.

How does imposing a prior distribution help improve the accuracy of the GAN? I know both entities (discriminator and generator) play a minimax game boosting each other's capability, but how does improving discriminator and generator improve the weights for encoder and decoder to match input image $x$ correctly with the output image?

(image taken from Makhzani et al)

# Answer
> 1 votes
In an adversarial autoencoder, the discriminator network can help generate a more suitable distribution of the latent parameters than would be produced through random selection. If the statistical distribution of the compressed representation is completely unaltered and done in a way as to maximize only the reconstruction accuracy, it is very hard to generate new, high-quality output images because we have to guess the distribution of these latent variables. In a variational autoencoder, this problem is solved by forcing the latent parameters (compressed representation) to conform to a normal (Gaussian) distribution, allowing us to easily generate new images. Using a discriminator to determine a suitable distribution increases the quality of the results produced because the constraints imposed are done in such a way that the reconstruction error can still remain very low and thus the output images are not blurry.

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


# Question
Title: Minimizing the maximum Manhattan distance
Given N points on a grid, find the number of points, such that the smallest maximal Manhattan distance from these points to any point on the grid is minimized. Also, determine the distance itself.

The points are inside a grid, –10000 ≤ Xi ≤ 10000 ; –10000 ≤ Yi ≤ 10000, N\<=100000.

In the example below the points are (1, 1), (6,1), (6,6), (3,4) and the smallest maximal Manhattan distance (equal to 5) is achieved from points (4,3), (5,2) (marked with E).

Is there an efficient algorithm to solve the problem? The restrictions are quite large so the brute force approach wouldn't work.

Edit: problem: http://varena.ro/problema/examen (RO language)

# Answer
> 0 votes
## One dimensionality of Manhattan-distance

Let us understand the Manhattan-distance.

Here is one remarkable phenomenon. Every one of the points (0,1), (1,0), (2, -1) is 6 distance away from every one of the points (3, 4), (4, 3), (5, 2). We can imagine that the former three points correspond to $1=0+1=1+0=2+(-1)$ on the number line and that the later three points correspond to $7=3+4=4+3=5+2$ on the number line as the distance between 1 and 7 is 6. We can say Manhattan-distance on the coordinate plane is one dimensional almost everywhere.

**One dimensionality of Manhattan-distance**. The Manhattan-distance of two points $(x\_1, y\_1)$ and $(x\_2, y\_2)$ is either $|(x\_1+y\_1)-(x\_2+y\_2)|$ or $|(x\_1-y\_1)-(x\_2-y\_2)|$, whichever is larger. $$ d((x\_1, y\_1),(x\_2, y\_2))= \max(|(x\_1+y\_1)-(x\_2+y\_2)|, |(x\_1-y\_1)-(x\_2-y\_2)|)$$

With this understanding, it is not difficult to construct the algorithm that computes minMax, the wanted minimum of the maximum Manhattan distance of a point to the given points and count, the number of all points that reach that minMax.

## Algorithm

1. Loop through all given points $(x,y)$ to compute the following.
    1. minSum, the minimum of all $x+y$.
    2. maxSum, the maximum of all $x+y$.
    3. minDiff, the minimum of all $x-y$.
    4. maxDiff, the maximum of all $x-y$.

According to the one dimensionality, we know minmax is the minimum of max((p+q)-minSum, maxSum-(p+q), (p-q)-minDiff, maxDiff-(p-q)) where (p,q) goes through all lattice points.

2. Let rangeSum = maxSum - minSum and rangeDiff = maxDiff - minDiff.
3. Let $s$ = min(rangeSum, rangeDiff) and $b$ = max(rangeSum, rangeDiff).
4. Let minMax = $b/2+1$ if both $s$ and $b$ are even and $(s-b)/2$ is odd. Otherwise, let minMax = $\lceil (b+1)/2\rceil$.

Once we have obtained the minMax, we can find all points whose maximum Manhattan-distance to points on the grid is minMax.

5. Let count = 0.
6. Run a nested loop, where `i` runs from (maxSum - minMax) to (minSum + minMax) and `j` runs from (maxDiff - minMax) to (minDiff + minMax), all inclusively. Whenever `i+j` is an even number, increase count by 1 since we get a point `((i+j)/2, (i-j)/2)` whose maximum Manhattan-distance to the given points is minMax.

## Time complexity

The only place that may run longer than $O(N)$ is the step 6. We can see that either (minSum + minMax) - (maxSum - minMax) \<= 1 or (minDiff + minMax) - (maxDiff - minMax) \<= 1 So the nested loops is basically one loop run at most twice. So step 6 takes at most $O(M)$ time, where $M$ is the maximum absolute value of the coordinates of the given points.

The algorithm above runs in $O(N + M)$ time, which should be faster enough to solve the original contest problem.

---

Here are two easy exercises.

**Exercise 1**. Prove one dimensionality of Manhattan-distance stated above. Show the algorithm above is correct.

**Exercise 2.** Speed up step 6 of the algorithm so that the step 6 will run in $O(1)$ time. The improved algorithm will run in $O(N)$ time.

# Answer
> 3 votes
Manhattan-distance balls are square and aligned with the diagonals, which makes this problem much simpler than the Euclidean equivalent.

Find an input point `P` with maximum `x+y`, an input point `Q` with minimum `x+y`, an input point `R` with maximum `x-y`, and an input point `S` with minimum `x-y`. The minimum maximum distance `d` is the maximum of `ceiling(((P.x+P.y) - (Q.x+Q.y))/2)` and `ceiling(((R.x-R.y) - (S.x-S.y))/2)` or sometimes that quantity plus one. Accordingly, for each center `C`, we can compute the bounds on `C.x+C.y` and `C.x-C.y` so that `(P.x+P.y) - (C.x+C.y) <= d` and similarly for `Q, R, S`. Then there's some simple formula to count the points in that rotated rectangle. If the count is zero, increase `d` and try again.

The overall running time is `O(N)`.

---
Tags: computational-geometry
---


title: Algorithm for MST connecting a subgraph

text:
# Question
Title: Algorithm for MST connecting a subgraph
I already know how to find the MST of a connected graph. This MST will have the least total weight and will connect **all** nodes in the graph.

However, this is a problem I have to deal with:

> Given a weighted graph $G=\\{V,E\\}$ and one of its subgraph $H$. Find a subset $E'$ of $E$ such that
>
> * If we clear out every edge outside of $E'$, $H$ is still connected.
> * The total weight of $E'$ is lowest possible.
>
> Note that $E'$ may contain edges that don't join two vertices in $H$, and any two vertices in $H$ may not necessarily be joined by an edge.

It is little different from the MST problem.

Firstly I thought that I only have to run MST algorithm in $H$, but I later found that this only work if any two vertices of $H$ is joined by an edge, not a series of edges.

How can I solve this problem? Thanks in advance.

# Answer
This is the Steiner Tree problem, specifically the Steiner Tree problem in graphs: the vertices in $H$ are the terminals. Unfortunately it's NP-hard, so it's very unlikely that a polynomial-time algorithm exists.

If $E$ describes a metric, then the minimum spanning tree on $H$ gives a 2-approximation.
> 1 votes

---
Tags: algorithms, minimum-spanning-tree
---


# Question
Title: Does converting adjacency matrix representation of graph of size $n \times n$ to adjacency list always require $O(n^2)$ time?
Assume that I have the adjacency matrix representation of a graph in $0,1$ values. Does converting it to a corresponding adjacency list representation **always** have a time complexity of $O(n^2)$?

# Answer
> 2 votes
"Nothing is always."

Without any prior knowledge, the worst case time-complexity of converting an adjacency matrix representation of a graph in 0,1 values to a corresponding adjacency list representation is $\Theta(n^2)$.

However, if we know the graph is a sparse matrix with number of edges $m=o(n^2)$ and its adjacency matrix is stored in some compressed format like Yale format, then we can expect a conversion takes $o(n^2)$ time.

# Answer
> 1 votes
Yes. An algorithm that converts an adjacency matrix to an adjacency list must always take $\Omega(n^2)$ time. Otherwise, there would be at least one entry of the matrix that is never read, and thus the algorithm would not know whether that edge should occur in the output (if the graph is directed). Thus, we could construct an input on which the algorithm produces the wrong result (by flipping the value of the matrix at an entry that is never read if it doesn't already produce a wrong result on that input). If the graph is undirected the same argument holds, we just have to observe that there are at least $n^2/2+1$ entries that are never read.

---
Tags: algorithms, graphs, asymptotics
---


title: Finding size of cache in blocks

text:
# Question
Title: Finding size of cache in blocks
Let's say I have a 64 kB Cache provided (i,e 2^18) which is direct mapped and block size is 16 byte = 2^5

Now, in the solution it says `m=size of cache in blocks = 4096 = 2^12`. This hasn't been provided in the question. So, how do we assume / derive size of cache in blocks was `2^12`.

If this is a static value, then does that changes if block size is increased to 32 bytes?

# Answer
The size of the cache in blocks is just the size of the cache in bytes divided by the size of a block in bytes. However, both the figures you give are wrong: 64 kB is 2^16 bytes, and 16 bytes is 2^4 bytes. Dividing we get 2^12.
> 1 votes

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


# Question
Title: Number Theory Problem from Local Selection Contest EPFL | ETHZ
This was a question from the 2016 local (selection) contest in ETHZ, You have a high-precision alarm clock with three operations:

1) reset wake-up time to midnight (00:00:00.000000)

2) modify the wake-up time by ± 1 microsecond (wrapping around at midnight).

You know your wake-up time ("hh:mm:ss.yyyyyy") for the next N consecutive days and want to modify the wake-up time accordingly. Any number of the above two operations can be executed at an arbitrary instant in time, at or after the start of day one.

Pressing the same button a million times can be quite frustrating. You came up with the following idea to reduce the number of button presses: Exactly 24h before day one, the alarm clock is unplugged, which makes the timer pause. You can plug it in again at a real-world time t0 chosen by you to resume the timer. Select this time such as to minimize the total number of operations required to ensure the clock rings at the correct time on each day. If there are multiple choices for t0, take the smallest one.

**Input:** The first lines contains a single number N, with 1 ≤ N ≤ 10^5. The following N lines contain the wake-up times in the form "hh:mm:ss.yyyyyy" (the letters standing for hours, minutes, seconds, microsecond respectively). It is guaranteed that the seconds and minutes do not exceed 59 and the hours do not exceed 23. In case the numbers can be written using less characters, they will have leading zeros.

**Output:** On the first line, print the number of operations (it is guaranteed that this numbers will be smaller than 10^18). On the second line, print the time t0 in the format "hh:mm:ss.yyyyyy".

The approach I tried was to formulate the problem as follows (any difference of times is assumed to be taken modulo 24):

1) We are given the timer is stopped at the start of day 0. Thus during day 0 (i.e. before start of day 1) the timer is resumed at some time $x$ (that is at time $x$, the timer displays 00:00:00.000000). Hence if for a given day $i$, the wake-up time is $w\_i$ then the alarm should be set to $w\_i - x$

2) The cost of setting timer for first wake up time necessarily includes the operation of resetting wake-up time to midnight and then increasing wake-up time (if $w\_1-x$ happens to be AM) or otherwise decreasing if the wake-up time is PM.

3) For the other days $j$ the wake-up time is minimum of setting alarm to time $w\_j - x$ starting from midnight and setting the alarm by increasing or decreasing from wake-up time of day before. So $min(w\_j-x, w\_j-w\_{j-1})$

However I do not know of an algorithm, greedy or number theoretic, which can solve this problem.

# Answer
The solution will be one of the alarm times so a solution would be to sort the times by increasing order and the earliest time that gives the minimum would be the solution. The proof is simple: Suppose the optimal time, $x=t\_0$, is not one of the alarm times. Further imagine a number line (or segment) spanning from 00:00:00.000 000 up to 23:59:59.999 999 now plot the points representing the wake up times. Clearly selecting time $x$ as the optimal choice will shift the points to the left by $x$ (if a point happens to hit left-most border of this segment then it will wrap around so it will end up at the right-most border). Now suppose there are $s$ points that we reach by resetting i.e. by starting from 00:00:00.000 000 (midnight) relative to alarm time not real time. Of these points $r$ will be by increasing time from midnight and $l$ by decreasing time from midnight. Suppose $l\>r$ (the other case is identical) so there are more points to which we decrease from midnight to, and graphically this would correspond to starting from the right-most border of the interval and going left to the desired points. Clearly, if we shift all points to the right so that the right-most of these points coincides with right-most border then we have gained a net advantage since we have decreased all the distance to the $l$ points by some constant, $c$, but increased distances to $r$ points by the same constant $c$ but since $l\>r$ we have a net decrease of $(l-r)c$.
> 0 votes

---
Tags: greedy-algorithms, number-theory
---